{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\"><i>Peter Norvig<br>2012; updated August 2019</i></div>\n",
    "\n",
    "# Weighing Twelve Balls on a Balance Scale \n",
    "\n",
    "> *You are given twelve identical-looking balls and a two-sided scale. One of the balls is of a different weight, although you don't know whether it's lighter or heavier. How can you use just three weighings of the scale to determine not only what the different ball is, but also whether it's lighter or heavier?*\n",
    "\n",
    "This is [a classic](https://en.wikipedia.org/wiki/Balance_puzzle) brain-teaser puzzle (first appearing in 1945), meant to be solved with paper and pencil.  But I want to solve not just this specific puzzle, but related puzzles where you can vary (a) the number of balls, (b) the number of weighings allowed, and (c) whether the odd ball might be heavier, lighter, or either, or neither. So I'll need a computer program, not a pencil. (I originally wrote this program in 2012, but am republishing it here in revised form because the puzzle was mentioned in the [538 Riddler](https://fivethirtyeight.com/features/which-billiard-ball-is-rigged/) for 16 August 2019. It also appeared in a [Numberplay](https://wordplay.blogs.nytimes.com/2014/07/21/12coin/) column in 2014 (with coins instead of balls) among other venues.)\n",
    "\n",
    "<p><center>\n",
    "    🎱🎱🎱🎱⚖🎱🎱🎱🎱\n",
    "</center>\n",
    "\n",
    "# Design\n",
    "\n",
    "Here are the concepts I'm dealing with:\n",
    "\n",
    "- **balls**: In the general case I have N balls. I'll represent them with a list like `[1, 2, 3]` for N = 3.\n",
    "- **possible oddballs**: Exactly one of the balls is different in its weight; I'll use the term **oddball** to indicate which ball is different, and how.\n",
    "I'll represent the situation where ball N is heavier as +N, and where ball N is lighter as -N.  With N = 3, the set of all possible oddballs is `{+1, -1, +2, -2, +3, -3}`. (As an extension that is not needed for the stated puzzle but is useful for similar puzzles: I'll represent the situation where all the balls weigh the same&mdash;no ball is odd&mdash;with `0`.)\n",
    "- **puzzle**: I'll express the puzzle stated above with `Puzzle(N=12, weighings=3)`. A puzzle is defined by the balls involved, the number of weighings allowed, and the possible oddballs. (I'll add a few complications later.)\n",
    "- **weighing**: I can weigh a collection of balls on the left versus a collection on the right, and the result will be that the left side is greater than, equal to, or less than the right in weight. I'll denote that with the call `weigh(L, R, oddball)`, which returns a string, `'gt'`, `'eq'`, or `'lt'`.\n",
    "- **weight**: I'll arbitrarily say that a normal ball weighs 100, a lighter ball 99, and a heavier ball 101.\n",
    "- **solution**: Given a puzzle, a solution is a **strategy tree** that can correctly discover the odd ball, whatever it is, in the allowable number of weighings. Since a tree with W weighings has 3<sup>W</sup> possible outcomes (leaf nodes), we can deduce that it is impossible to find a solution in W weighings if there are more than 3<sup>W</sup> possible oddballs.\n",
    "- **strategy tree**: A tree whose leaf nodes are all oddballs (ints), and whose interior nodes have 5 components:  `Tree(L, R, gt, eq, lt)` is a node where `L` and `R` are the collections of balls to be weighed, and `gt`, `eq`, and `lt` are branches for subtrees corresponding to the three possible results of the weighing. (I'll also use `None` to mean \"could not find a valid tree.\")\n",
    "- **following a path in a tree**: I'll use `follow(tree, oddball)` to say *follow the path through the tree, doing each weighing under the assumption of the given oddball, and return the leaf node reached by the path&mdash;the oddball that the tree predicts.* Note that the function `follow` gets to see what the oddball is, but the `tree` never gets direct access to that; the tree has to figure it out by doing weighings.\n",
    "- **valid tree**: A tree is a valid solution to a puzzle if no branch uses more than the allowable number of weighings, and if, for every possible oddball in the puzzle, following the path through the tree correctly returns that oddball as the answer. I'll use `valid(tree, puzzle)` for this.\n",
    "\n",
    "Note: I have an idea for the definition of the `Puzzle` class: by default, the oddballs are all the \"lighter\" and \"heavier\" versions of the puzzle's balls. But if you want a different kind of puzzle, I'll allow two options: you can specify the keyword argument `oddballs=` and give a set of oddballs; whatever you want. Or you can specify the keyword argument `oddities`, whose value can be any subset of `{-1, 0, +1}`, where `-1` means \"any one ball might be lighter,\" `+1` means \"any one ball might be heavier,\" and `0` means \"it might be that no ball is odd; they all weigh the same.\"\n",
    "\n",
    "\n",
    "# Implementation\n",
    "\n",
    "Let's start implementing the concepts:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "import random\n",
    "\n",
    "#### Types\n",
    "\n",
    "Ball = Oddball = int\n",
    "\n",
    "class Puzzle:\n",
    "    \"Represent a specific ball-weighing puzzle.\"\n",
    "    def __init__(self, N=12, weighings=3, oddities={-1, +1}, oddballs=None):\n",
    "        # If `oddballs` is None, compute them via `oddities`.\n",
    "        self.balls     = list(range(1, N + 1))\n",
    "        self.weighings = weighings\n",
    "        self.oddballs  = (oddballs if oddballs is not None else\n",
    "                          {b * o for b in self.balls for o in oddities})\n",
    "        \n",
    "Tree = namedtuple('Tree', 'L, R, gt, eq, lt')\n",
    "\n",
    "#### Functions\n",
    "    \n",
    "def weigh(L, R, oddball) -> str:\n",
    "    \"Weigh balls L against balls R, given the oddball; return 'gt', 'eq', or 'lt'.\"\n",
    "    diff = sum(weight(b, oddball) for b in L) - sum(weight(b, oddball) for b in R)\n",
    "    return ('gt' if diff > 0 else\n",
    "            'lt' if diff < 0 else\n",
    "            'eq')\n",
    "\n",
    "def weight(ball, oddball) -> int: \n",
    "    \"How heavy is this ball (given that we know what the oddball is)?\"\n",
    "    return 101 if +ball == oddball else 99 if -ball == oddball else 100\n",
    "    \n",
    "def solve(puzzle) -> Tree or None:\n",
    "    \"Return a valid tree (one that solves the puzzle), or None.\"\n",
    "    tree = find_tree(puzzle, puzzle.oddballs, puzzle.weighings)\n",
    "    return tree if valid(tree, puzzle) else None\n",
    "    \n",
    "def follow(tree, oddball) -> Oddball:\n",
    "    \"Follow a path through the tree and return the oddball that the tree leads us to.\"\n",
    "    if is_leaf(tree):\n",
    "        return tree\n",
    "    else:\n",
    "        branch = weigh(tree.L, tree.R, oddball)\n",
    "        return follow(getattr(tree, branch), oddball)\n",
    "    \n",
    "def valid(tree, puzzle) -> bool:\n",
    "    \"Does the strategy tree solve the puzzle correctly for all possible oddballs?\"\n",
    "    return (tree is not None and\n",
    "            depth(tree) <= puzzle.weighings and \n",
    "            all(follow(tree, oddball) == oddball \n",
    "                for oddball in puzzle.oddballs))\n",
    "\n",
    "def depth(tree) -> int:\n",
    "    \"Maximum depth (number of weighings) in tree.\"\n",
    "    return (0 if is_leaf(tree) or tree is None\n",
    "            else 1 + max(depth(tree.gt), depth(tree.eq), depth(tree.lt)))\n",
    "\n",
    "def is_leaf(node): return isinstance(node, Oddball)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try out some of these functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3,\n",
       " [1, 2, 3, 4, 5, 6, 7, 8],\n",
       " {-8, -7, -6, -5, -4, -3, -2, -1, 1, 2, 3, 4, 5, 6, 7, 8})"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p8 = Puzzle(8) \n",
    "\n",
    "p8.weighings, p8.balls, p8.oddballs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eq'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# If we weigh balls 1, 2 against 3, 4, and the oddball is that 5 is lighter, the result should be 'eq'\n",
    "weigh([1, 2], [3, 4], -5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weight(1, oddball=-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "99"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weight(5, oddball=-5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_leaf(-3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_leaf(Tree([1], [2], +1, +3, +2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Finding a Valid Tree\n",
    "\n",
    "Now we've got all the pieces we need to find a valid tree to solve a puzzle. The key concept is that a **weighing** gives us information by making a **partition** of the possible **oddballs** into branches for each of the three possible weighing results: `gt`, `eq`, or `lt`. If each of the partitions is small enough, subsequent weighings can handle each of them. Here's what I mean by a partition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(L, R, oddballs) -> dict:\n",
    "    \"Build a dict that partitions the possible outcomes (oddballs) resulting from weighing L versus R.\"\n",
    "    part = dict(gt=set(), eq=set(), lt=set())\n",
    "    for odd in oddballs:\n",
    "        part[weigh(L, R, odd)].add(odd)\n",
    "    return part"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, with 12 balls, if we weigh balls 1 and 2 on the left versus 11 and 12 on the right, then there are 4 ways  the left side can be greater than the right: either 11 or 12 is lighter or  1 or 2 is heavier. Similarly there are 4 ways of getting a `lt` weighing result. The remaining 16 possibilities&mdash;balls 3 through 10 being either heavier or lighter&mdash;show up in the `eq` branch of the partition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'gt': {-12, -11, 1, 2},\n",
       " 'eq': {-10, -9, -8, -7, -6, -5, -4, -3, 3, 4, 5, 6, 7, 8, 9, 10},\n",
       " 'lt': {-2, -1, 11, 12}}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p12 = Puzzle(12, 3)\n",
    "\n",
    "partition([1, 2], [11, 12], p12.oddballs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If this was the first weighing in our strategy tree, could we go on to solve the puzzle in 3 weighings? **No!** With two remaining weighings we can handle at most  3 &times; 3 = 9 possibilities; here we have 16 possibilities in the `eq` branch, which is too many. We call this a **bad partition**.\n",
    "\n",
    "The following is a **good partition** because each of the branches has 8 possibilities, and 8 is less than 9. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'gt': {-12, -11, -10, -9, 1, 2, 3, 4},\n",
       " 'eq': {-8, -7, -6, -5, 5, 6, 7, 8},\n",
       " 'lt': {-4, -3, -2, -1, 9, 10, 11, 12}}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partition([1, 2, 3, 4], [9, 10, 11, 12], p12.oddballs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Note: being a good partition does not guarantee that the puzzle is solvable from there; but being a bad partition guarantees that it is not solvable. Also note that this is a good partition with 2 remaining weighings, but would be a bad partition with only one remaining weighing.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So now we have a viable approach to implementing `find_tree`:\n",
    "\n",
    "   - We call `find_tree(puzzle, oddballs, weighings)`. At the top level, the oddballs and number of weighings come from the puzzle. At recursive levels, we will reduce the number of oddball possibilities according to the partition, and the number of remaining weighings by 1 each time.\n",
    "   - We handle trivial cases when there are zero or one oddballs remaining, or no weighings remaining.\n",
    "   - Otherwise, we generate random partitions of the balls, and examine the good ones.\n",
    "   - Given a good partition, all we have to do is find good trees (i.e. not `None`) for each of the three branches. If we can find that, return the tree as a solution.\n",
    "   - If we can't find good trees for any partition, return `None` to indicate failure.\n",
    "   \n",
    "The rest of the work is done by `good_partitions`:\n",
    "\n",
    "   - We randomly select two lists of balls to be weighed, `L` and `R`, both of length `B`.\n",
    "   - We systematically consider all reasonable values of `B`. (All values from 1 up to 1/3 the number of balls, rounded up.)\n",
    "   - We then see what partition `L` and `R` gives us.\n",
    "   - If it is good, the function yields the `(L, R, partition)` tuple.\n",
    "   - In any case, we repeat the process 100 times. That number was chosen to have a very good chance of randomly selecting a good partition for solvable puzzles, and of terminating in just a few seconds for unsolvable puzzles. (If I wanted to solve puzzles  with thousands of balls, I would come back and improve `good_partitions`.)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_tree(puzzle, oddballs, weighings) -> Tree or Oddball or None:\n",
    "    \"Find a strategy tree that covers all the oddballs in the given number of weighings.\"\n",
    "    if len(oddballs) == 1:\n",
    "        return next(iter(oddballs)) # One possibility left; we're done; leaf node\n",
    "    elif len(oddballs) == 0:\n",
    "        return 0                    # No oddball\n",
    "    elif weighings == 0:\n",
    "        return None                 # No solution within allowable weighings; fail\n",
    "    else:\n",
    "        for L, R, part in good_partitions(puzzle, oddballs, weighings - 1):\n",
    "            subtrees = {r: find_tree(puzzle, part[r], weighings - 1) for r in part}\n",
    "            if None not in subtrees.values(): \n",
    "                return Tree(L, R, **subtrees)\n",
    "    \n",
    "def good_partitions(puzzle, oddballs, weighings, tries=100):\n",
    "    \"Yield random (L, R, partition) tuples with no partition branch longer than 3**weighings.\"\n",
    "    balls = list(puzzle.balls)\n",
    "    for _ in range(tries): \n",
    "        for B in range(1, (len(balls) + 2) // 3 + 1):\n",
    "            random.shuffle(balls)\n",
    "            L, R = balls[:B], balls[-B:]\n",
    "            part = partition(L, R, oddballs)\n",
    "            longest = max(part.values(), key=len)\n",
    "            if len(longest) <= 3 ** weighings:\n",
    "                yield L, R, part"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we see that  `good_partitions` does its job:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([12, 2, 8, 5],\n",
       " [3, 4, 7, 9],\n",
       " {'gt': {-9, -7, -4, -3, 2, 5, 8, 12},\n",
       "  'eq': {-11, -10, -6, -1, 1, 6, 10, 11},\n",
       "  'lt': {-12, -8, -5, -2, 3, 4, 7, 9}})"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(good_partitions(p12, p12.oddballs, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving Some Puzzles\n",
    "\n",
    "Now we're ready to solve puzzles!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Tree(L=[4, 12, 9, 7], R=[10, 8, 1, 3], gt=Tree(L=[6, 12, 11, 3], R=[8, 5, 1, 7], gt=Tree(L=[3, 8, 12], R=[6, 5, 4], gt=12, eq=-1, lt=-8), eq=Tree(L=[12, 7, 1], R=[9, 10, 3], gt=-10, eq=4, lt=9), lt=Tree(L=[5, 4, 10], R=[7, 2, 9], gt=0, eq=-3, lt=7)), eq=Tree(L=[9, 5, 1, 11], R=[10, 3, 8, 6], gt=Tree(L=[6, 3, 11], R=[12, 1, 7], gt=11, eq=5, lt=-6), eq=Tree(L=[5], R=[2], gt=-2, eq=0, lt=2), lt=Tree(L=[9, 5, 4], R=[3, 11, 7], gt=-11, eq=6, lt=-5)), lt=Tree(L=[2, 5, 3, 6], R=[1, 9, 4, 8], gt=Tree(L=[8, 10, 9, 11], R=[6, 12, 2, 4], gt=-4, eq=3, lt=-9), eq=Tree(L=[2, 12], R=[7, 8], gt=-7, eq=10, lt=-12), lt=Tree(L=[8, 11], R=[2, 4], gt=8, eq=1, lt=0)))"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(p12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, that's hard to read&mdash;my bad. Let's look at a much easier puzzle: 3 balls, 1 weighing allowed, and the odd ball can only be lighter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Tree(L=[1], R=[2], gt=-2, eq=-3, lt=-1)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = solve(Puzzle(3, 1, {-1}))\n",
    "tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tree says you weigh one ball against another (leaving the third unweighed), and the three possible weighing results tell you which of the three balls  is lighter. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Prettier Output\n",
    "\n",
    "Let's make the output easier to read. I'll use `[1·2·3·4]⚖[9·10·11·12] ➔` to mean *\"Weigh balls 1,2,3,4 versus 9,10,11,12 to get a result...\"*. I'll indent each interior node in the tree, and I'll use `>:` to mean *the result when the left hand side is greater than the right in weight is...*  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def do(puzzle):\n",
    "    \"Print the solution to the puzzle as indented text.\"\n",
    "    print(indented(solve(puzzle)))\n",
    "    \n",
    "def indented(tree, i=0, prefix='') -> str:\n",
    "    \"Pretty, indented string representing a strategy tree.\"\n",
    "    if tree == 0 or tree == None:\n",
    "        return f'{prefix}{tree}'\n",
    "    elif is_leaf(tree):\n",
    "        return f'{prefix}{tree:+d}'\n",
    "    else:\n",
    "        subtrees = (indented(tree.gt, i+1, '>:'), indented(tree.eq, i+1, '=:'), indented(tree.lt, i+1, '<:'))\n",
    "        indent   = ('' if i == 0 else ('\\n' + ' ' * 5 * i))\n",
    "        return f'{indent}{prefix}{side(tree.L)}⚖{side(tree.R)} ➔ {\" \".join(subtrees)})'\n",
    "    \n",
    "def side(balls) -> str: return str(sorted(balls)).replace(', ', '·')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also, note that at the root node of a tree, there's no sense randomly shuffling the balls&mdash;the only choice that matters is how many balls, `B`, to put on each side. Putting `1·2·3·4` on the left is no different than `3·7·9·12`, because each ball is undifferentiated at the start. I'll alter `good_partitions` to do this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def good_partitions(puzzle, oddballs, weighings, tries=100):\n",
    "    \"Yield random (L, R, partition) tuples with no partition branch longer than 3**weighings.\"\n",
    "    at_root = (oddballs == puzzle.oddballs)\n",
    "    balls   = sorted(puzzle.balls)\n",
    "    for _ in range(1 if at_root else tries): \n",
    "        for B in range(1, (len(balls) + 2) // 3 + 1):\n",
    "            if not at_root: random.shuffle(balls)\n",
    "            L, R = balls[:B], balls[-B:]\n",
    "            part = partition(L, R, oddballs)\n",
    "            longest = max(part.values(), key=len)\n",
    "            if len(longest) <= 3 ** weighings:\n",
    "                yield L, R, part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]⚖[3] ➔ >:-3 =:-2 <:-1)\n"
     ]
    }
   ],
   "source": [
    "# 3 balls, 1 weighing, only lighter balls possible\n",
    "do(Puzzle(3, 1, {-1}))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]⚖[3] ➔ \n",
      "     >:[1]⚖[2] ➔ >:+1 =:-3 <:0) \n",
      "     =:[3]⚖[2] ➔ >:-2 =:0 <:+2) \n",
      "     <:[1]⚖[2] ➔ >:0 =:+3 <:-1))\n"
     ]
    }
   ],
   "source": [
    "# 3 balls, 2 weighings, lighter or heavier balls possible\n",
    "do(Puzzle(3, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4]⚖[9·10·11·12] ➔ \n",
      "     >:[4·7·9·12]⚖[5·8·10·11] ➔ \n",
      "          >:[4·8·10]⚖[1·3·7] ➔ >:+4 =:-11 <:-10) \n",
      "          =:[3·4·9·10]⚖[1·5·11·12] ➔ >:+3 =:+2 <:+1) \n",
      "          <:[6]⚖[12] ➔ >:-12 =:-9 <:0)) \n",
      "     =:[5·6·8·12]⚖[3·4·9·11] ➔ \n",
      "          >:[8]⚖[6] ➔ >:+8 =:+5 <:+6) \n",
      "          =:[8·9·12]⚖[3·6·7] ➔ >:-7 =:0 <:+7) \n",
      "          <:[1·3·5]⚖[6·9·11] ➔ >:-6 =:-8 <:-5)) \n",
      "     <:[3·4·12]⚖[1·2·10] ➔ \n",
      "          >:[1·10·11]⚖[2·4·8] ➔ >:-2 =:+12 <:-1) \n",
      "          =:[1·3]⚖[7·9] ➔ >:0 =:+11 <:+9) \n",
      "          <:[4·5·8·9]⚖[3·6·11·12] ➔ >:-3 =:+10 <:-4)))\n"
     ]
    }
   ],
   "source": [
    "# The original puzzle with 12 balls, 3 weighings\n",
    "do(p12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4]⚖[9·10·11·12] ➔ \n",
      "     >:[1·9·11]⚖[3·10·12] ➔ \n",
      "          >:[1·10]⚖[5·8] ➔ >:+1 =:-12 <:-10) \n",
      "          =:[2·10]⚖[3·12] ➔ >:+2 =:+4 <:0) \n",
      "          <:[2·6·10·11]⚖[1·7·9·12] ➔ >:-9 =:+3 <:-11)) \n",
      "     =:[2·7·9·12]⚖[3·4·5·6] ➔ \n",
      "          >:[1·5·10]⚖[2·6·11] ➔ >:-6 =:+7 <:-5) \n",
      "          =:[1·2·10]⚖[5·8·12] ➔ >:-8 =:0 <:+8) \n",
      "          <:[6·12]⚖[5·11] ➔ >:+6 =:-7 <:+5)) \n",
      "     <:[3·4·8·11]⚖[1·5·7·10] ➔ \n",
      "          >:[10·12]⚖[1·3] ➔ >:-1 =:+11 <:0) \n",
      "          =:[8·10·12]⚖[3·6·9] ➔ >:+12 =:-2 <:+9) \n",
      "          <:[4·10]⚖[1·12] ➔ >:+10 =:-3 <:-4)))\n"
     ]
    }
   ],
   "source": [
    "# A different solution to the same puzzle\n",
    "do(p12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I note that the traditional answer to the puzzle weighs 4 balls on each side of the first weighing, three balls on the second weighing, and 2 balls on the third weighing. But my program is not so orderly. It always weighs 4 balls on the first weighing, but from there it can vary; it has no inclination to minimize the number of balls on each side of the scale, or to make one branch of the tree be similar to another branch.\n",
    "\n",
    "# Other Puzzles: 3 Weighings\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can do **12 balls in 3 weighings** even when we add in the possibility that all the balls weigh the same (we use `0` to denote this situation):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4]⚖[9·10·11·12] ➔ \n",
      "     >:[4·6·9·11]⚖[2·5·7·12] ➔ \n",
      "          >:[3·4]⚖[7·8] ➔ >:+4 =:-12 <:0) \n",
      "          =:[3·9]⚖[1·4] ➔ >:+3 =:-10 <:+1) \n",
      "          <:[7·11·12]⚖[4·6·9] ➔ >:-9 =:+2 <:-11)) \n",
      "     =:[2·6·8]⚖[7·9·10] ➔ \n",
      "          >:[1·4·5·11]⚖[6·7·10·12] ➔ >:-7 =:+8 <:+6) \n",
      "          =:[5·7·9·12]⚖[1·4·6·8] ➔ >:+5 =:0 <:-5) \n",
      "          <:[2·3·11·12]⚖[4·7·8·10] ➔ >:-8 =:-6 <:+7)) \n",
      "     <:[4·5·9]⚖[1·3·10] ➔ \n",
      "          >:[1·7]⚖[3·8] ➔ >:-3 =:+9 <:-1) \n",
      "          =:[2·5·12]⚖[6·7·9] ➔ >:+12 =:+11 <:-2) \n",
      "          <:[2·3·4·5]⚖[6·8·11·12] ➔ >:0 =:+10 <:-4)))\n"
     ]
    }
   ],
   "source": [
    "do(Puzzle(12, 3, {-1, 0, +1}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can we solve the **13-balls in 3 weighings** puzzle, which has 26 possibilities? After all, 26 is less than 3<sup>3</sup>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "do(Puzzle(13))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**No**, and the reason is that there is no first weighing that partitions the 26 possibilities into 9/9/8; the best we can do is partition into 8/10/8 or 10/6/10, and 10 possibilities can't be distinguished in the remaining two weighings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'gt': {-13, -12, -11, -10, 1, 2, 3, 4},\n",
       " 'eq': {-9, -8, -7, -6, -5, 5, 6, 7, 8, 9},\n",
       " 'lt': {-4, -3, -2, -1, 10, 11, 12, 13}}"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partition([1, 2, 3, 4], [10, 11, 12, 13], Puzzle(13).oddballs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'gt': {-13, -12, -11, -10, -9, 1, 2, 3, 4, 5},\n",
       " 'eq': {-8, -7, -6, 6, 7, 8},\n",
       " 'lt': {-5, -4, -3, -2, -1, 9, 10, 11, 12, 13}}"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partition([1, 2, 3, 4, 5], [9, 10, 11, 12, 13], Puzzle(13).oddballs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can do **27 balls in 3 weighings** if we know that the odd ball can only be lighter, not heavier:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4·5·6·7·8·9]⚖[19·20·21·22·23·24·25·26·27] ➔ \n",
      "     >:[9·10·13·20·21·22]⚖[7·11·15·23·24·27] ➔ \n",
      "          >:[2·4·7·8·12·14·17·23]⚖[3·6·11·13·18·19·21·24] ➔ >:-24 =:-27 <:-23) \n",
      "          =:[1·6·10·13·19·22·23]⚖[3·9·12·18·21·26·27] ➔ >:-26 =:-25 <:-19) \n",
      "          <:[4·5·6·13·14·18·19·20·25]⚖[2·7·9·12·15·17·21·24·26] ➔ >:-21 =:-22 <:-20)) \n",
      "     =:[3·7·8·12·13·18·19·21·25]⚖[1·4·5·6·10·16·17·22·24] ➔ \n",
      "          >:[3·4·10·26]⚖[8·16·19·20] ➔ >:-16 =:-17 <:-10) \n",
      "          =:[3·11]⚖[14·24] ➔ >:-14 =:-15 <:-11) \n",
      "          <:[1·4·6·16·17·18]⚖[3·5·12·24·26·27] ➔ >:-12 =:-13 <:-18)) \n",
      "     <:[3·6·8·10·12·17·19·21·25]⚖[1·2·5·13·14·16·22·23·24] ➔ \n",
      "          >:[1·3·14·15·16·25·27]⚖[2·6·7·19·22·23·24] ➔ >:-2 =:-5 <:-1) \n",
      "          =:[1·7·8·12·14·18·23]⚖[9·13·16·20·21·22·26] ➔ >:-9 =:-4 <:-7) \n",
      "          <:[1·2·6·10·13·17·22·23·27]⚖[3·7·9·11·15·20·21·25·26] ➔ >:-3 =:-8 <:-6)))\n"
     ]
    }
   ],
   "source": [
    "do(Puzzle(27, 3, {-1}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we can do **26 balls** under the condition that either one ball is lighter or all the balls weigh the same. In both these puzzles there are 27 possibilities, the maximum number we can handle in 3 weighings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4·5·6·7·8·9]⚖[18·19·20·21·22·23·24·25·26] ➔ \n",
      "     >:[3·6·8·9·11·17·19·21·23]⚖[1·4·5·7·10·15·18·20·26] ➔ \n",
      "          >:[9·12·17·18·21·22]⚖[1·7·15·23·25·26] ➔ >:-26 =:-20 <:-18) \n",
      "          =:[5·12·13·14·15·17·21·25]⚖[1·2·4·6·8·9·16·24] ➔ >:-24 =:-22 <:-25) \n",
      "          <:[2·8·19·24]⚖[6·10·21·25] ➔ >:-21 =:-23 <:-19)) \n",
      "     =:[5·9·11·13·15·18·19·21]⚖[2·3·4·10·14·16·20·25] ➔ \n",
      "          >:[2·10·20]⚖[7·16·17] ➔ >:-16 =:-14 <:-10) \n",
      "          =:[3·7·11·12·14·25·26]⚖[5·9·15·17·18·19·24] ➔ >:-17 =:0 <:-12) \n",
      "          <:[1·11·20]⚖[12·13·16] ➔ >:-13 =:-15 <:-11)) \n",
      "     <:[2·5·9·10·20·21·26]⚖[1·6·8·11·12·15·23] ➔ \n",
      "          >:[6·19·20]⚖[1·9·23] ➔ >:-1 =:-8 <:-6) \n",
      "          =:[2·3·8·12]⚖[7·15·16·26] ➔ >:-7 =:-4 <:-3) \n",
      "          <:[8·9·10·19·26]⚖[1·4·5·15·18] ➔ >:-5 =:-2 <:-9)))\n"
     ]
    }
   ],
   "source": [
    "do(Puzzle(26, 3, {-1, 0}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a puzzle with **25 balls** with an unusual set of possibilities: either one of the odd-numbered balls is heavier, or one of the even-numbered balls is lighter, or no ball is odd."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, -24, -22, -20, -18, -16, -14, -12, -10, -8, -6, -4, -2}\n"
     ]
    }
   ],
   "source": [
    "N = 25\n",
    "p = Puzzle(N, 3, oddballs={(+b if b % 2 else -b) for b in range(N + 1)})\n",
    "print(p.oddballs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4·5·6·7·8·9]⚖[17·18·19·20·21·22·23·24·25] ➔ \n",
      "     >:[2·4·6·9·13·17·20·21·25]⚖[3·7·10·11·12·14·15·18·22] ➔ \n",
      "          >:[4·5·9·15·19·22]⚖[1·2·8·12·16·23] ➔ >:+9 =:-18 <:-22) \n",
      "          =:[5·6·7·9·16·19·25]⚖[1·3·11·14·17·21·23] ➔ >:+5 =:-24 <:+1) \n",
      "          <:[9·12·21·25]⚖[7·11·18·20] ➔ >:-20 =:+3 <:+7)) \n",
      "     =:[5·7·9·12·13·16·17·23]⚖[2·6·8·10·14·18·20·25] ➔ \n",
      "          >:[2·3·9·17·22]⚖[8·13·14·21·23] ➔ >:-14 =:-10 <:+13) \n",
      "          =:[2·3·6·8·13·14·15·19·22]⚖[1·4·9·11·12·16·17·18·20] ➔ >:+15 =:0 <:+11) \n",
      "          <:[3·4·10·17·21·25]⚖[5·8·11·12·20·24] ➔ >:-12 =:-16 <:0)) \n",
      "     <:[4·7·9·13·16·17·24]⚖[5·6·8·12·18·21·25] ➔ \n",
      "          >:[1·2·12·15·22·23]⚖[7·8·10·13·14·17] ➔ >:-8 =:-6 <:+17) \n",
      "          =:[1·3·9·15·20·22·24]⚖[2·8·11·13·19·21·25] ➔ >:-2 =:+23 <:+19) \n",
      "          <:[1·10·14·21]⚖[9·17·22·25] ➔ >:+21 =:-4 <:+25)))\n"
     ]
    }
   ],
   "source": [
    "do(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another variation: **27 balls, 3 weighings**, the odd ball can only be lighter, but one ball (number 27) is radioactive and can't be touched or placed on the balance scale. It might, however be the lighter ball, and you still need to report it as such if it is. (That happens when all three weighings are equal.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4·5·6·7·8·9]⚖[18·19·20·21·22·23·24·25·26] ➔ \n",
      "     >:[3·7·10·13·17·18·24·25]⚖[1·2·4·9·12·21·23·26] ➔ \n",
      "          >:[8·18·23]⚖[7·13·21] ➔ >:-21 =:-26 <:-23) \n",
      "          =:[5·10·12·14·18·19·21]⚖[1·3·8·11·22·24·25] ➔ >:-22 =:-20 <:-19) \n",
      "          <:[22·25·26]⚖[20·23·24] ➔ >:-24 =:-18 <:-25)) \n",
      "     =:[2·3·6·7·11·12·13·19·26]⚖[1·4·8·10·15·16·21·22·24] ➔ \n",
      "          >:[4·12·13·15·26]⚖[2·10·17·24·25] ➔ >:-10 =:-16 <:-15) \n",
      "          =:[3·9·12·15·17·26]⚖[8·11·14·21·24·25] ➔ >:-14 =:-27 <:-17) \n",
      "          <:[7·9·10·13·18·23·24]⚖[1·5·6·11·20·22·25] ➔ >:-11 =:-12 <:-13)) \n",
      "     <:[4·5·8·23]⚖[2·3·6·15] ➔ \n",
      "          >:[1·3·8·9·15·16·18·20·22]⚖[2·5·10·11·12·21·24·25·26] ➔ >:-2 =:-6 <:-3) \n",
      "          =:[2·4·9·10·18·19·21·24·26]⚖[5·6·7·8·14·15·16·22·23] ➔ >:-7 =:-1 <:-9) \n",
      "          <:[4·11·14·21]⚖[2·3·5·18] ➔ >:-5 =:-8 <:-4)))\n"
     ]
    }
   ],
   "source": [
    "do(Puzzle(26, 3, oddballs=range(-27, 0)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4 Weighings\n",
    "\n",
    "We can tackle larger puzzles. With 4 weighings, we can theoretically handle up to 3<sup>4</sup> = 81 possibilities. Can we solve for **40 balls**?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "p40 = Puzzle(40, 4)\n",
    "\n",
    "do(p40)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unfortunately, **no**. We always end up with at least one branch with 28 possibilities, but we need 27 or less:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition_sizes(puzzle, B):\n",
    "    \"How big is each branch of a partition with B balls on both sides?\"\n",
    "    part = partition(puzzle.balls[:B], puzzle.balls[-B:], puzzle.oddballs)\n",
    "    return {branch: len(part[branch]) for branch in part}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'gt': 26, 'eq': 28, 'lt': 26}"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partition_sizes(p40, 13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'gt': 28, 'eq': 24, 'lt': 28}"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partition_sizes(p40, 14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How about **39 balls**, with the possibility that no ball is odd. That's 39 &times; 2 + 1 = 79 possibilities, but it turns out we can find a good partition, and a solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "p39 = Puzzle(39, 4, {-1, 0, +1})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'gt': 26, 'eq': 27, 'lt': 26}"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partition_sizes(p39, 13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4·5·6·7·8·9·10·11·12·13]⚖[27·28·29·30·31·32·33·34·35·36·37·38·39] ➔ \n",
      "     >:[2·3·6·12·14·24·26·28·29·30·37·38]⚖[1·4·5·17·19·23·25·27·31·32·33·36] ➔ \n",
      "          >:[4·6·13·17·18·24·25·33·37·38·39]⚖[1·2·5·10·12·16·20·23·28·31·36] ➔ \n",
      "               >:[8·16·18·27·28·35·36·37·39]⚖[5·7·10·12·14·20·30·31·34] ➔ >:-31 =:+6 <:-36) \n",
      "               =:[8·11·12·22·24·29·30·34·35·37·38]⚖[3·4·13·14·15·17·18·19·23·26·32] ➔ >:-32 =:-27 <:+3) \n",
      "               <:[2·3·11·13·17·30·31·38]⚖[5·7·12·25·27·28·29·35] ➔ >:+2 =:-33 <:+12)) \n",
      "          =:[1·2·9·12·13·15·18·21·31]⚖[3·8·10·11·14·16·36·38·39] ➔ \n",
      "               >:[4·5·17·19·23·32·35·38]⚖[9·10·21·24·27·29·37·39] ➔ >:-39 =:+13 <:+9) \n",
      "               =:[2·9·13·16·19·24·29·31·32·37·39]⚖[1·4·7·10·12·17·23·26·27·30·34] ➔ >:-34 =:-35 <:+7) \n",
      "               <:[2·6·8·15·18·22·24·26·34·39]⚖[7·10·12·13·14·23·28·31·36·38] ➔ >:+8 =:+11 <:+10)) \n",
      "          <:[1·5·11·12·22·23·29·30·33·38]⚖[2·3·13·17·20·27·28·31·34·35] ➔ \n",
      "               >:[3·4·5·10·11·17·28·29·34·37]⚖[7·14·16·22·23·24·27·33·36·39] ➔ >:+5 =:+1 <:-28) \n",
      "               =:[3·4·12·30·34]⚖[2·7·10·27·28] ➔ >:+4 =:-37 <:0) \n",
      "               <:[17·29]⚖[8·38] ➔ >:-38 =:-30 <:-29))) \n",
      "     =:[1·7·8·9·12·14·17·18·26·29·32·37]⚖[3·4·5·15·19·20·23·24·28·30·34·38] ➔ \n",
      "          >:[3·13·15·18·23·26·28·33·35·36·39]⚖[2·6·9·10·11·14·16·24·29·31·34] ➔ \n",
      "               >:[2·10·12·14·18·19·24·30·35·39]⚖[1·4·5·13·17·20·22·29·31·33] ➔ >:+18 =:+26 <:-24) \n",
      "               =:[3·10·11·14·19·23·27·30·34]⚖[5·9·12·18·20·25·28·32·35] ➔ >:-20 =:+17 <:-19) \n",
      "               <:[7·9·11·24]⚖[4·8·14·15] ➔ >:-15 =:-23 <:+14)) \n",
      "          =:[4·9·13·20·31·32·39]⚖[7·8·16·21·22·26·35] ➔ \n",
      "               >:[1·3·9·13·14·15·20·21·24·28·33]⚖[4·5·6·16·17·23·27·30·35·37·39] ➔ >:-16 =:-22 <:-21) \n",
      "               =:[8·23·29·32·35]⚖[9·20·25·27·37] ➔ >:-25 =:0 <:+25) \n",
      "               <:[8·9·13·19·21·27·31·36·37]⚖[3·5·10·17·22·26·30·34·38] ➔ >:+21 =:+16 <:+22)) \n",
      "          <:[1·2·3·16·17·20·23·26·28·32·34·38·39]⚖[4·5·8·10·14·15·21·22·27·30·33·35·37] ➔ \n",
      "               >:[5·9·15·16·17·18·25·27·30·37·38]⚖[2·7·12·14·19·22·23·32·34·35·39] ➔ >:-14 =:+20 <:+23) \n",
      "               =:[2·5·6·9·10·12·15·17·21·23·30·36·39]⚖[1·3·7·13·14·18·24·25·28·31·33·34·38] ➔ >:-18 =:+19 <:+24) \n",
      "               <:[2·10·13·15·23·26·31·35·36]⚖[5·9·16·19·20·27·29·33·38] ➔ >:+15 =:-17 <:-26))) \n",
      "     <:[1·10·12·13·15·27·31·33·34·35·37]⚖[3·5·8·14·22·23·26·28·32·36·39] ➔ \n",
      "          >:[2·3·11·14·15·20·23·26·27·34·39]⚖[7·8·10·12·18·19·22·28·30·31·37] ➔ \n",
      "               >:[2·5·7·10·11·17·22·29·34·37·38·39]⚖[3·9·12·13·15·21·23·27·31·32·33·36] ➔ >:+34 =:-8 <:+27) \n",
      "               =:[1·5·8·11·12·13·15·26·29·30·32·35]⚖[3·6·7·10·17·24·25·27·34·36·37·39] ➔ >:+35 =:+33 <:-5) \n",
      "               <:[2·4·5·6·7·15·18·22·25·31·34·39]⚖[1·13·23·24·26·29·30·32·35·36·37·38] ➔ >:+31 =:-3 <:+37)) \n",
      "          =:[4·5·11·14·35·38]⚖[7·9·21·24·29·32] ➔ \n",
      "               >:[2·4·6·9·13·23·31·32·33]⚖[1·7·10·11·15·16·22·26·34] ➔ >:-7 =:+38 <:-9) \n",
      "               =:[2·4·9·13·14·19·26·27·30·38·39]⚖[8·11·12·16·18·20·23·28·33·35·37] ➔ >:+30 =:-6 <:-2) \n",
      "               <:[3·17·19·35]⚖[4·12·20·29] ➔ >:-4 =:-11 <:+29)) \n",
      "          <:[5·11·13·15·19·25·34·37·38]⚖[2·9·10·12·24·27·30·32·36] ➔ \n",
      "               >:[6·12·28]⚖[4·16·21] ➔ >:0 =:-10 <:-12) \n",
      "               =:[4·9·10·22·23·27·30·32·39]⚖[2·3·14·16·20·25·28·33·38] ➔ >:+39 =:-1 <:+28) \n",
      "               <:[3·14·17·18·19·21·22·23·29·30·32·33·38]⚖[1·4·8·10·11·16·24·25·26·27·31·36·37] ➔ >:+32 =:-13 <:+36))))\n"
     ]
    }
   ],
   "source": [
    "do(p39)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How about **80 balls** under the condition that no ball can be heavier (thus, 81 possibilities):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4·5·6·7·8·9·10·11·12·13·14·15·16·17·18·19·20·21·22·23·24·25·26·27]⚖[54·55·56·57·58·59·60·61·62·63·64·65·66·67·68·69·70·71·72·73·74·75·76·77·78·79·80] ➔ \n",
      "     >:[2·3·4·7·8·10·12·18·24·34·38·40·44·49·53·58·59·62·64·72·73·76·77·78]⚖[11·14·15·20·22·23·25·27·31·32·35·42·43·50·52·54·55·56·60·63·65·66·70·79] ➔ \n",
      "          >:[1·2·4·11·14·24·30·32·37·39·40·46·48·49·52·53·54·56·60·61·62·67·76·77]⚖[12·17·18·20·22·23·25·28·29·31·33·34·36·41·44·45·51·58·63·65·66·68·69·73] ➔ \n",
      "               >:[11·14·15·16·20·22·26·33·40·42·47·57·60·65·68·69·70·77]⚖[1·6·10·17·19·25·30·32·35·43·58·59·62·64·66·73·74·78] ➔ >:-66 =:-63 <:-65) \n",
      "               =:[2·3·10·12·13·14·15·17·28·30·37·39·47·50·63·65·79]⚖[1·4·6·8·20·23·26·27·34·38·40·43·54·55·61·67·71] ➔ >:-55 =:-70 <:-79) \n",
      "               <:[3·4·9·16·23·24·33·41·42·49·53·56·57·63·64·66·69·70·71·77·79·80]⚖[6·7·11·12·13·15·17·18·19·34·35·37·44·46·47·51·58·59·60·62·67·75] ➔ >:-60 =:-54 <:-56)) \n",
      "          =:[4·8·13·14·17·18·20·22·23·24·27·30·40·41·48·50·53·67·70·71·75]⚖[2·5·7·16·19·26·28·32·35·39·44·51·54·55·61·64·68·69·72·77·78] ➔ \n",
      "               >:[6·15·35·38·41·42·63·65·68]⚖[19·28·33·40·55·57·59·66·69] ➔ >:-69 =:-61 <:-68) \n",
      "               =:[9·16·23·66·73·74]⚖[17·18·29·32·55·80] ➔ >:-80 =:-57 <:-74) \n",
      "               <:[1·3·11·13·15·17·36·47·71·78·79]⚖[2·20·27·33·52·56·57·59·67·76·80] ➔ >:-67 =:-75 <:-71)) \n",
      "          <:[9·13·14·15·16·19·21·44·47·49·53·56·64·66·68·71·74·77·78·80]⚖[6·7·8·10·11·24·28·31·32·37·39·40·50·51·55·58·62·69·72·79] ➔ \n",
      "               >:[2·5·9·11·22·29·33·54·55·56·62·68·76·80]⚖[7·10·13·15·16·17·18·20·28·36·40·58·64·79] ➔ >:-58 =:-72 <:-62) \n",
      "               =:[6·9·15·19·29·41·66·73]⚖[1·23·31·51·59·60·70·78] ➔ >:-59 =:-76 <:-73) \n",
      "               <:[4·5·6·12·18·19·23·29·31·39·40·43·45·47·57·61·62·65·66·70·73·77]⚖[2·9·16·22·25·27·30·37·48·49·53·60·63·69·71·72·74·75·76·78·79·80] ➔ >:-78 =:-64 <:-77))) \n",
      "     =:[6·11·12·14·16·24·26·27·28·29·31·36·37·38·44·50·51·54·59·60·67·72·75·77·78·80]⚖[1·2·4·7·10·17·18·20·21·22·30·32·34·42·43·46·48·49·53·56·57·61·64·69·74·76] ➔ \n",
      "          >:[3·4·11·17·20·21·22·23·24·28·29·32·36·39·41·43·49·54·58·62·66·68·72·74·75·79]⚖[5·6·12·16·18·19·25·26·30·34·35·38·42·44·45·50·59·61·65·67·69·70·76·77·78·80] ➔ \n",
      "               >:[1·11·14·16·21·30·31·33·41·43·45·46·49·51·54·62·63·77·80]⚖[2·3·10·15·20·22·24·25·29·40·42·48·50·52·64·65·68·70·71] ➔ >:-42 =:-34 <:-30) \n",
      "               =:[1·3·6·9·19·21·23·24·26·31·39·49·53·59·64·69·80]⚖[2·4·27·30·36·38·40·41·46·50·54·57·61·63·68·71·72] ➔ >:-46 =:-48 <:-53) \n",
      "               <:[9·14·15·18·20·22·27·28·43·52·63·65·77·79]⚖[1·7·11·21·26·30·41·42·49·56·67·68·69·74] ➔ >:-49 =:-32 <:-43)) \n",
      "          =:[1·2·4·6·11·17·21·24·31·35·40·41·43·54·60·63·65·67·73·76]⚖[10·14·15·18·26·28·36·37·39·45·47·48·56·58·59·64·71·74·75·79] ➔ \n",
      "               >:[2·11·13·16·24·25·28·39·40·59·72·76·79]⚖[3·21·31·38·47·50·52·57·58·74·77·78·80] ➔ >:-47 =:-45 <:-39) \n",
      "               =:[18·25·30·34·52·57·64·75·76]⚖[13·21·33·45·53·62·70·72·80] ➔ >:-33 =:0 <:-52) \n",
      "               <:[1·9·35·52·69·73]⚖[4·10·31·40·42·61] ➔ >:-40 =:-41 <:-35)) \n",
      "          <:[5·6·9·15·20·26·30·32·33·35·37·38·39·43·45·50·53·56·58·62·66·73·74·77·79·80]⚖[2·4·8·10·11·12·14·16·18·22·23·28·40·42·44·46·48·51·52·57·60·65·68·69·71·78] ➔ \n",
      "               >:[1·2·3·9·24·27·35·39·45·49·51·59·62·63·70·71·76·77]⚖[16·19·21·22·30·37·38·41·42·43·44·46·50·53·64·65·73·75] ➔ >:-44 =:-28 <:-51) \n",
      "               =:[2·6·12·15·18·24·28·36·42·43·54·57·58·62·63·64·65·66]⚖[3·5·9·10·19·20·21·23·27·29·33·47·48·60·68·75·78·79] ➔ >:-29 =:-31 <:-36) \n",
      "               <:[1·3·6·7·9·12·14·41·43·50·54·61·64·65]⚖[5·11·22·25·29·32·33·35·38·49·55·62·70·71] ➔ >:-38 =:-37 <:-50))) \n",
      "     <:[1·6·14·15·21·23·24·25·26·29·32·38·42·53·62·65·66·67·70·71·73·76·79]⚖[3·7·8·10·13·16·17·18·20·31·34·37·39·41·47·49·54·56·58·60·64·68·75] ➔ \n",
      "          >:[2·6·13·16·20·27·32·33·43·46·47·48·59·61·66·67·68·71·72·74·76·78]⚖[3·5·10·12·18·23·25·28·29·30·31·34·40·45·52·54·58·60·64·73·75·80] ➔ \n",
      "               >:[2·6·18·24·35·36·43·46·50·52·56·58·63·64·66·68·74·76]⚖[4·5·8·9·10·12·16·17·21·26·48·51·53·60·73·75·77·78] ➔ >:-10 =:-3 <:-18) \n",
      "               =:[3·5·17·20·21·25·26·27·32·43·44·45·47·52·58·64·71·72·75·79]⚖[7·11·12·13·29·33·34·37·41·46·49·51·54·57·62·66·68·70·74·77] ➔ >:-7 =:-8 <:-17) \n",
      "               <:[4·8·12·15·18·20·21·27·28·33·38·46·47·61·70·71·79]⚖[3·6·10·16·17·26·30·31·34·35·37·48·59·64·68·73·80] ➔ >:-16 =:-13 <:-20)) \n",
      "          =:[1·5·12·21·22·35·38·40·52·58·61·65]⚖[4·19·25·27·29·46·48·50·53·56·59·76] ➔ \n",
      "               >:[8·10·12·17·27·58·76]⚖[11·15·19·46·54·62·63] ➔ >:-19 =:-4 <:-27) \n",
      "               =:[2·24·25·27·33·42·48·62·67]⚖[9·17·22·31·43·44·59·64·73] ➔ >:-9 =:-11 <:-2) \n",
      "               <:[5·18·19·23·34·41·63·69·70]⚖[2·4·17·22·26·39·43·61·68] ➔ >:-22 =:-12 <:-5)) \n",
      "          <:[2·3·5·7·8·9·14·17·19·20·21·22·25·27·31·32·35·38·39·45·52·53·55·57·65·69·78]⚖[10·12·18·23·24·26·29·30·33·34·37·40·43·44·58·59·60·61·64·66·68·71·72·73·74·75·77] ➔ \n",
      "               >:[4·12·13·24·25·35·44·49·52·56·57·59·61·62·63·64·70·78]⚖[6·7·18·19·20·23·40·41·42·45·46·47·51·67·68·71·72·79] ➔ >:-23 =:-26 <:-24) \n",
      "               =:[1·7·12·19·22·29·36·40·42·58·59·61·62·71·79·80]⚖[13·15·16·30·32·35·41·44·56·60·65·66·70·75·76·78] ➔ >:-15 =:-6 <:-1) \n",
      "               <:[14·34·36·39·41·53·70·74·76·79]⚖[3·5·6·21·28·42·49·60·62·68] ➔ >:-21 =:-25 <:-14))))\n"
     ]
    }
   ],
   "source": [
    "do(Puzzle(80, 4, {-1, 0}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looking good (except that the output is longer than the line length, and so again is hard to read).\n",
    "\n",
    "# 5 Weighings\n",
    "\n",
    "With 5 weighings, 3<sup>5</sup> = 243, so I might be able to handle up to 121 lighter-or-heavier balls (242 possibilities). Let's try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "do(Puzzle(121, 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'gt': 82, 'eq': 78, 'lt': 82}"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partition_sizes(Puzzle(121, 5), 41)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nope, that didn't work. Let's back off to 2 &times; 120 + 1 = 241 possibilities:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4·5·6·7·8·9·10·11·12·13·14·15·16·17·18·19·20·21·22·23·24·25·26·27·28·29·30·31·32·33·34·35·36·37·38·39·40]⚖[81·82·83·84·85·86·87·88·89·90·91·92·93·94·95·96·97·98·99·100·101·102·103·104·105·106·107·108·109·110·111·112·113·114·115·116·117·118·119·120] ➔ \n",
      "     >:[4·6·7·11·13·14·18·21·23·35·36·38·40·42·47·49·61·65·69·71·73·74·75·78·79·80·86·88·93·95·98·99·100·104·105·113·114·115·116]⚖[2·8·9·12·15·17·19·20·25·27·29·34·37·41·44·45·46·53·55·58·62·64·66·72·76·84·90·91·92·96·97·101·102·103·108·110·111·117·118] ➔ \n",
      "          >:[10·21·22·26·34·36·43·46·48·49·50·51·53·56·57·61·62·66·67·68·70·71·82·89·91·93·100·110·111·114·119·120]⚖[4·6·13·14·16·17·24·35·39·40·41·42·47·52·55·59·60·65·75·81·90·92·94·96·98·101·102·103·105·109·115·117] ➔ \n",
      "               >:[1·6·8·14·17·18·23·25·26·28·29·35·38·48·49·51·58·60·66·69·76·81·82·85·87·88·93·94·100·102·103·108·112·115]⚖[2·7·9·12·15·19·24·27·32·36·37·39·41·43·53·55·56·59·61·63·65·70·73·80·84·90·92·97·99·106·107·110·111·117] ➔ \n",
      "                    >:[4·5·66·71·77·90·107]⚖[8·19·44·50·65·104·117] ➔ >:-117 =:-92 <:-90) \n",
      "                    =:[1·2·4·5·7·14·17·18·25·26·37·40·43·46·47·49·52·56·63·74·75·76·77·78·79·84·85·88·95·105·108·109·110·118]⚖[3·12·19·21·29·33·48·50·51·53·54·58·62·64·68·71·73·83·92·98·100·101·102·103·104·106·107·111·112·114·116·117·119·120] ➔ >:-101 =:-96 <:+21) \n",
      "                    <:[1·14·18·28·34·37·39·48·53·61·64·66·67·81·96·99·105·108·118]⚖[4·13·21·33·36·41·44·59·60·63·70·83·84·90·91·95·103·109·115] ➔ >:-103 =:-102 <:+36)) \n",
      "               =:[3·6·12·13·15·16·17·20·23·24·25·27·37·38·40·46·50·54·55·61·62·69·75·76·84·87·92·95·98·109·111·112·113·114·116·118·119]⚖[1·4·8·10·11·19·21·26·31·33·34·39·43·48·49·51·56·57·58·59·65·67·71·74·78·81·82·86·88·91·93·105·106·107·108·115·120] ➔ \n",
      "                    >:[2·3·8·11·17·25·28·30·32·35·38·40·41·59·60·68·73·74·75·85·88·91·95·108·110]⚖[12·13·14·24·27·29·39·45·55·58·62·65·70·79·83·86·90·96·103·104·111·112·117·118·119] ➔ >:+38 =:+23 <:-108) \n",
      "                    =:[17·18·41·47·67·70·71·84·88·106·109·112·114·116·117·120]⚖[5·7·13·22·24·25·39·46·49·72·78·80·93·100·101·102] ➔ >:+18 =:-97 <:+7) \n",
      "                    <:[11·15·20·22·23·26·29·32·40·43·55·59·60·64·70·73·76·79·80·82·83·84·85·86·90·94·100·101·115·117]⚖[2·5·8·17·19·21·25·28·30·34·35·37·39·46·47·51·56·57·74·91·93·95·99·106·107·110·111·113·114·120] ➔ >:+11 =:-118 <:-84)) \n",
      "               <:[5·6·9·11·17·19·24·28·29·30·31·35·38·44·48·49·57·64·65·73·75·79·84·85·88·90·93·94·95·98·101·103·105·106·112·120]⚖[2·10·13·14·16·18·20·21·23·32·34·37·39·40·47·50·54·55·56·60·67·69·70·71·72·77·78·80·81·86·100·109·110·114·116·117] ➔ \n",
      "                    >:[14·15·38·42·59·63·66·116]⚖[6·27·70·80·93·109·110·118] ➔ >:-110 =:+35 <:+6) \n",
      "                    =:[11·26·45·58·78·81·87·94·95·97·105·118]⚖[4·12·13·19·28·48·64·74·83·84·88·91] ➔ >:-91 =:-111 <:+4) \n",
      "                    <:[6·16·20·26·35·40·50·55·63·64·68·69·71·76·79·82·83·84·92·107·117·119]⚖[12·13·21·23·25·27·32·38·45·46·52·53·59·66·72·74·85·96·97·99·101·109] ➔ >:+40 =:+14 <:+13))) \n",
      "          =:[4·9·21·26·27·28·33·37·39·40·49·52·55·56·60·61·64·69·79·80·81·83·84·89·90·91·95·96·105·106·107·110·113·114·120]⚖[2·5·8·11·14·15·18·19·24·25·29·30·48·50·54·59·68·71·77·78·82·85·86·88·92·93·94·97·99·103·108·112·117·118·119] ➔ \n",
      "               >:[6·13·29·32·33·34·35·36·39·41·42·45·50·54·66·70·73·74·82·88·89·91·92·93·97·102·110·112·115·117·119]⚖[1·2·3·12·14·18·20·21·25·38·47·48·53·56·60·65·67·76·77·81·84·85·87·95·96·104·107·111·116·118·120] ➔ \n",
      "                    >:[1·5·6·9·14·16·18·19·20·35·39·40·41·42·49·53·54·62·63·65·66·79·85·87·92·93·103·108·111·112·113·114·119·120]⚖[2·4·12·15·23·24·25·27·29·30·31·34·44·47·51·55·56·59·60·67·70·76·81·82·84·86·89·98·100·104·105·106·110·118] ➔ >:+39 =:+33 <:-85) \n",
      "                    =:[4·5·19·23·24·30·37·38·66·75·77·81·90·106·115]⚖[10·17·18·26·32·34·49·61·70·89·94·96·101·110·118] ➔ >:-94 =:+28 <:+26) \n",
      "                    <:[8·12·13·17·48·54·56·68·86·90·116·119]⚖[11·20·43·72·74·77·80·82·88·89·99·101] ➔ >:-82 =:-112 <:-119)) \n",
      "               =:[1·4·6·8·9·13·16·19·20·31·35·38·41·42·48·54·58·66·69·71·74·78·80·82·85·86·87·88·89·95·96·97·108·112·113·117·118]⚖[2·5·7·10·12·17·21·23·25·26·32·33·36·39·40·43·45·50·51·55·59·60·62·65·67·72·76·81·84·92·98·99·101·102·114·119·120] ➔ \n",
      "                    >:[1·4·5·6·7·8·12·17·18·20·23·24·28·32·35·52·56·59·61·68·77·83·86·94·99·102·103·106·116·117·118·119]⚖[2·3·11·14·16·34·37·38·46·48·53·58·62·63·64·65·66·67·72·73·81·87·89·90·92·100·108·109·110·112·113·114] ➔ >:+1 =:+31 <:+16) \n",
      "                    =:[4·15·20·22·24·36·85·91·101·103·104·106·116]⚖[3·9·29·32·33·65·67·70·74·75·79·93·107] ➔ >:+22 =:-109 <:+3) \n",
      "                    <:[28·32·39·42·52·54·67·74·87·92]⚖[7·33·56·57·70·73·78·84·101·117] ➔ >:+32 =:+10 <:-87)) \n",
      "               <:[6·7·8·10·13·18·20·23·24·31·43·44·48·50·51·52·54·61·64·72·80·82·83·85·91·93·99·108·109·110·112·118·120]⚖[1·5·9·11·12·19·22·28·33·35·36·38·42·47·55·56·59·60·74·75·79·84·90·95·98·101·103·106·107·114·115·116·119] ➔ \n",
      "                    >:[1·5·7·9·17·21·28·32·44·60·71·74·79·100·101]⚖[3·13·19·23·24·38·39·47·50·81·83·86·93·107·116] ➔ >:-107 =:-106 <:+24) \n",
      "                    =:[3·16·24·28·30·38·40·41·53·54·55·60·65·67·68·80·84·89·94·97·99·103·106·109·113]⚖[6·8·11·12·23·26·31·32·34·39·43·47·56·62·63·66·71·75·77·79·98·100·107·114·118] ➔ >:+30 =:-81 <:-89) \n",
      "                    <:[5·7·8·16·24·45·46·51·60·69·71·79·80·81·82·83·89·101·110]⚖[14·17·26·27·29·31·33·34·43·54·55·63·66·76·77·95·106·118·119] ➔ >:+5 =:-120 <:-83))) \n",
      "          <:[8·12·22·25·28·29·32·36·37·40·49·51·56·63·65·68·72·73·75·78·87·88·92·93·97·99·101·104·109·111·112·118]⚖[1·2·4·14·17·19·20·33·34·41·44·47·55·57·58·62·66·67·70·77·79·80·82·89·90·98·105·107·108·113·114·120] ➔ \n",
      "               >:[2·4·6·9·17·20·21·24·25·29·35·36·38·41·45·55·76·77·79·88·96·105·113·114]⚖[7·22·28·32·39·43·47·49·57·58·67·72·73·74·83·91·93·97·98·99·107·115·118·120] ➔ \n",
      "                    >:[7·25·39·47·49·50·56·66·84·105]⚖[13·20·29·48·61·67·73·85·86·93] ➔ >:+25 =:-98 <:+29) \n",
      "                    =:[6·12·13·32·35·39·41·55·66·89·96·105]⚖[5·8·16·38·40·43·74·75·82·93·95·113] ➔ >:+12 =:+37 <:+8) \n",
      "                    <:[3·8·18·19·21·32·35·39·40·43·47·51·52·65·66·69·74·89·94·98·108·114]⚖[6·7·15·28·29·36·45·58·79·81·82·84·86·87·93·101·105·106·111·117·118·120] ➔ >:-105 =:-113 <:-114)) \n",
      "               =:[7·8·15·17·22·31·32·42·47·53·64·65·75·77·82·84·87·88·89·93·94·96·99·100·106·108·119]⚖[4·6·9·10·11·35·36·37·40·43·49·50·56·57·61·66·71·72·78·80·95·98·104·107·111·114·115] ➔ \n",
      "                    >:[7·8·13·17·21·22·23·28·30·31·35·37·45·46·51·78·83·90·115·117·118]⚖[4·9·14·24·32·57·60·65·71·77·86·95·96·98·99·100·109·110·111·113·116] ➔ >:-95 =:+15 <:-115) \n",
      "                    =:[2·8·14·18·23·25·36·44·46·70·84·98·110·112·114]⚖[6·16·27·51·54·57·62·64·74·86·87·92·94·111·115] ➔ >:-86 =:-116 <:+27) \n",
      "                    <:[10·61·69·90·112·113·117]⚖[22·40·43·59·96·100·114] ➔ >:-100 =:+9 <:0)) \n",
      "               <:[4·7·12·16·19·22·23·40·46·48·49·56·58·61·63·68·69·74·79·80·83·85·86·87·89·92·95·104·111·112·120]⚖[3·9·10·11·17·20·26·27·28·29·35·36·45·50·51·52·53·66·67·71·73·76·81·93·98·99·102·103·107·108·117] ➔ \n",
      "                    >:[2·4·24·26·32·35·46·50·53·57·62·70·71·72·81·86·87·89·90·103·106·109·111·112·118]⚖[14·19·22·30·31·33·42·45·54·59·61·67·69·74·79·83·92·93·96·98·100·105·110·113·116] ➔ >:-93 =:-99 <:+19) \n",
      "                    =:[1·2·12·19·23·35·48·65·73·79·84·89·91·103·108·109]⚖[15·16·20·25·32·34·37·44·47·66·78·83·96·102·104·114] ➔ >:+2 =:-88 <:+34) \n",
      "                    <:[7·14·17·22·31·45·52·54·59·71·73·76·97·104·114·119]⚖[4·12·19·25·35·39·43·46·48·60·61·63·80·101·102·110] ➔ >:+17 =:+20 <:-104)))) \n",
      "     =:[2·7·17·18·21·31·32·40·41·42·43·45·51·52·53·56·57·63·66·69·72·73·75·78·79·82·88·95·96·99·100·107·111·117]⚖[3·4·5·6·10·12·13·19·23·25·26·33·35·44·47·49·55·58·59·65·67·68·74·84·85·89·102·105·106·112·113·114·115·118] ➔ \n",
      "          >:[1·2·9·11·13·14·15·21·22·24·30·34·39·44·51·52·62·63·65·70·72·77·81·86·87·89·91·92·93·95·98·100·103·105·109·116]⚖[3·6·7·8·10·16·17·25·26·27·28·32·33·41·42·43·45·46·47·49·50·55·57·60·61·68·74·75·76·79·110·111·112·113·117·118] ➔ \n",
      "               >:[1·5·6·10·19·33·34·39·42·45·47·49·51·62·72·73·98·104·113·114·115·116·120]⚖[4·12·14·15·20·22·24·26·35·43·44·63·68·70·76·78·82·83·85·97·100·102·110] ➔ \n",
      "                    >:[2·8·11·14·21·22·24·28·32·39·41·47·48·49·51·53·56·57·63·64·67·73·74·75·80·90·92·93·94·99·108·109·112·113·117·120]⚖[3·5·9·13·25·30·31·33·35·38·40·43·44·45·46·50·54·55·58·60·61·62·71·72·76·78·81·85·98·100·102·105·114·115·116·118] ➔ >:+51 =:-68 <:+72) \n",
      "                    =:[6·13·15·22·41·42·55·69·73·86·91·98·100·102·105·116·118]⚖[3·9·10·38·50·51·53·54·71·72·74·94·99·101·107·109·111] ➔ >:-74 =:+52 <:-55) \n",
      "                    <:[3·5·8·11·13·14·27·29·39·44·46·54·56·61·65·66·69·70·74·75·80·83·86·90·106·109·113·116·119·120]⚖[6·17·18·22·23·24·26·34·36·37·41·42·43·47·52·53·57·58·59·60·63·64·72·91·93·99·101·105·107·114] ➔ >:-47 =:-49 <:+63)) \n",
      "               =:[1·9·17·18·22·25·29·31·33·39·41·51·54·57·58·59·60·63·65·66·70·75·78·81·88·97·110·118]⚖[2·3·5·7·16·28·37·38·46·50·56·64·67·76·80·82·86·89·96·101·102·103·105·108·111·116·119·120] ➔ \n",
      "                    >:[2·6·25·38·40·41·54·79·82·93·104·105]⚖[9·11·60·66·67·68·71·81·86·91·101·120] ➔ >:-67 =:+78 <:+66) \n",
      "                    =:[22·29·43·48·53·82·98·104·119]⚖[3·20·36·37·51·57·61·69·115] ➔ >:+53 =:+73 <:+69) \n",
      "                    <:[8·17·26·39·40·56·59·76·83·91·97·100·108]⚖[6·12·21·31·37·47·55·70·75·82·95·106·119] ➔ >:+56 =:-58 <:-59)) \n",
      "               <:[1·4·5·7·8·11·25·31·32·34·38·40·45·47·51·61·66·67·70·74·77·79·80·81·82·85·86·87·89·94·98·100·103·110·115·116·117·118·119]⚖[2·6·12·14·16·17·21·23·27·35·36·39·41·42·52·56·58·60·62·63·64·65·68·69·71·72·73·75·76·84·91·92·96·102·105·111·112·113·114] ➔ \n",
      "                    >:[14·29·30·32·35·44·45·63·65·74·97]⚖[17·20·57·67·68·85·91·94·105·111·115] ➔ >:+45 =:+79 <:-65) \n",
      "                    =:[4·7·17·37·41·44·46·50·51·57·77·83·92·100·110·114]⚖[2·20·21·22·23·27·40·52·53·59·60·62·70·97·99·113] ➔ >:+57 =:+43 <:-44) \n",
      "                    <:[8·9·10·13·18·30·42·46·47·51·53·59·71·73·79·82·95·96·111·112·117]⚖[11·23·24·35·41·58·60·62·67·70·76·80·83·90·93·99·101·107·109·115·116] ➔ >:+42 =:+75 <:+41))) \n",
      "          =:[1·2·8·13·14·19·21·24·29·35·44·54·55·60·63·64·66·70·75·78·86·87·89·91·94·98·106·111·116·117·119·120]⚖[6·12·20·28·30·31·32·33·37·38·46·47·59·62·67·71·72·73·74·77·80·82·88·97·99·103·104·107·109·110·113·114] ➔ \n",
      "               >:[5·11·18·19·21·24·27·29·35·37·39·41·45·46·58·62·63·68·69·70·73·83·87·88·95·96·107·108·113·116·117·118·119·120]⚖[1·2·7·9·10·12·22·23·36·40·47·48·49·50·52·53·64·65·67·72·74·75·77·80·81·85·89·94·98·99·101·105·109·115] ➔ \n",
      "                    >:[10·12·20·24·29·40·46·61·63·70·77·108·109]⚖[7·30·39·47·58·66·68·76·89·96·106·118·119] ➔ >:+70 =:-80 <:-77) \n",
      "                    =:[12·32·54·55·69·71]⚖[3·31·34·81·93·113] ➔ >:+54 =:+60 <:-71) \n",
      "                    <:[1·3·6·13·17·22·28·34·41·49·52·55·56·68·75·77·91·95·99·104·111·117]⚖[19·24·26·32·45·47·53·54·57·62·64·76·88·90·98·101·103·106·107·116·119·120] ➔ >:-62 =:-46 <:+64)) \n",
      "               =:[9·25·30·45·48·51·56·61·71·88·93·96·97·98·99·102·120]⚖[13·31·40·42·43·46·49·60·63·69·73·75·76·78·106·113·114] ➔ \n",
      "                    >:[14·20·32·48·65·68·76·83·93·99·108·115·116]⚖[13·17·21·22·29·35·40·49·52·55·58·67·103] ➔ >:+48 =:+61 <:-76) \n",
      "                    =:[15·48·50·51·69·83·89·108]⚖[6·23·29·32·100·105·110·120] ➔ >:+50 =:0 <:-50) \n",
      "                    <:[6·18·20·22·29·40·43·46·72·73·79·81·102·105·113]⚖[12·25·38·57·60·61·65·69·75·76·83·87·88·93·104] ➔ >:-61 =:-48 <:+76)) \n",
      "               <:[3·5·7·10·12·21·23·25·31·34·43·45·47·48·49·53·54·55·57·59·63·69·79·80·81·82·85·89·93·95·98·102·103·104·105·113·115]⚖[8·13·18·32·38·39·40·41·42·44·50·52·56·61·62·64·65·66·70·71·73·75·76·83·88·92·96·101·107·108·109·110·111·114·116·117·120] ➔ \n",
      "                    >:[11·16·17·21·28·33·43·51·53·55·58·70·79·80·84·86·87·96·106·107·109·117]⚖[5·8·12·15·19·23·24·44·61·63·67·71·74·78·81·90·94·100·114·115·116·120] ➔ >:+80 =:-64 <:-70) \n",
      "                    =:[3·11·12·19·20·22·23·28·37·42·43·46·54·58·61·66·67·68·74·76·78·82·86·87·90·99·101·108·110·112·114·115]⚖[6·15·24·26·32·36·40·44·49·53·59·62·64·69·71·77·79·80·81·83·84·85·92·93·96·97·104·106·111·116·117·120] ➔ >:+46 =:-60 <:+77) \n",
      "                    <:[15·20·25·35·51·67·71·81·95·96·109]⚖[12·18·53·62·73·76·80·91·92·115·120] ➔ >:+71 =:-54 <:+62))) \n",
      "          <:[1·2·3·11·12·14·16·18·20·25·28·30·32·35·41·44·45·50·53·55·56·60·67·75·76·77·80·83·85·87·88·90·98·102·107·108·111·119·120]⚖[4·6·7·10·13·15·21·23·24·26·29·36·37·42·43·47·48·52·57·59·62·64·65·74·78·79·82·89·91·95·96·99·103·105·112·113·114·115·118] ➔ \n",
      "               >:[1·6·9·13·14·16·23·26·46·48·54·57·62·67·68·69·71·75·78·85·92·95·97·100·101·104·113·115·117]⚖[3·5·7·8·11·15·22·25·34·35·37·38·43·49·52·55·59·70·77·80·82·84·86·87·99·116·118·119·120] ➔ \n",
      "                    >:[4·11·13·19·21·25·29·34·41·43·44·45·46·57·62·63·67·86·90·97·98·100·104·105·120]⚖[1·10·14·28·30·35·38·39·48·51·54·59·60·68·71·76·78·81·84·85·91·96·113·114·115] ➔ >:+67 =:-52 <:-43) \n",
      "                    =:[4·19·25·31·53·66·71·73·79·84·88]⚖[7·16·20·34·37·42·45·47·65·89·100] ➔ >:-42 =:+44 <:-79) \n",
      "                    <:[1·9·11·19·31·32·34·41·51·56·57·63·64·66·67·69·71·84·85·92·100·112]⚖[6·12·16·30·42·50·52·58·62·72·76·78·80·81·88·93·105·106·107·109·110·114] ➔ >:-78 =:+55 <:-57)) \n",
      "               =:[2·6·9·10·12·15·16·20·23·25·31·38·42·43·45·46·48·51·53·54·57·58·68·73·75·78·83·90·93·98·99·102·106·109·114·117·118·119]⚖[3·5·8·11·14·17·18·19·21·26·28·30·32·34·35·36·40·49·60·61·67·71·72·76·80·81·82·86·87·91·96·101·110·111·112·113·115·120] ➔ \n",
      "                    >:[4·9·18·19·30·32·34·36·41·56·57·67·68·72·86·93·94·104·107·114·117]⚖[7·15·17·22·25·31·44·46·48·54·60·62·63·76·77·85·97·98·100·101·106] ➔ >:+68 =:+58 <:-72) \n",
      "                    =:[2·12·27·29·42·66·68·74·75·87·100·101·102·103·106·107·108·109·117·118]⚖[3·9·23·30·39·46·53·58·62·69·76·82·85·88·89·98·111·115·116·119] ➔ >:-69 =:-63 <:-66) \n",
      "                    <:[11·12·27·31·37·38·39·44·46·54·55·67·71·72·73·75·78·79·81·86·88·96·97·101·103·105·106·116·117·118]⚖[4·7·17·20·21·26·29·30·35·51·52·59·60·63·66·69·80·84·87·90·92·95·99·102·104·109·111·112·113·119] ➔ >:-51 =:+49 <:-73)) \n",
      "               <:[3·4·11·15·18·25·26·27·29·36·38·45·49·53·54·59·60·65·66·77·78·85·87·98·99·105·113·115]⚖[2·8·9·14·17·20·23·30·39·43·47·51·61·63·70·71·75·81·90·91·92·97·101·104·106·112·117·118] ➔ \n",
      "                    >:[4·12·21·26·28·32·36·37·38·43·48·50·52·57·61·65·66·67·68·69·75·76·81·82]⚖[1·8·19·22·29·30·39·40·42·53·56·58·72·87·94·97·98·100·104·107·109·113·117·118] ➔ >:+65 =:+59 <:-75) \n",
      "                    =:[7·10·17·26·31·40·41·50·53·57·61·68·70·74·75·76·85·96·97·110·117]⚖[3·4·16·18·25·35·42·45·46·47·54·59·69·77·86·89·92·102·108·114·116] ➔ >:+74 =:-56 <:-41) \n",
      "                    <:[3·19·29·35·38·39·43·46·48·49·55·60·73·74·95·109·114·118]⚖[10·13·15·16·40·42·45·47·58·62·64·75·82·85·89·111·112·115] ➔ >:-45 =:-53 <:+47)))) \n",
      "     <:[4·5·7·10·12·19·20·24·25·30·32·33·39·44·49·51·52·54·55·56·62·63·66·69·70·75·82·88·89·92·96·97·105·106·107·110·111·114·115·117]⚖[1·6·8·11·14·15·16·22·27·29·34·37·40·42·43·46·47·50·53·57·61·67·68·73·74·78·79·81·86·87·90·93·94·99·100·108·112·113·116·118] ➔ \n",
      "          >:[10·13·14·17·20·21·24·26·27·30·33·35·36·40·41·45·46·48·50·51·55·62·68·71·72·73·77·84·89·97·99·102·104·109·111·115·119]⚖[3·6·8·22·23·28·29·37·39·42·44·49·53·54·57·59·66·70·74·75·78·79·81·82·83·86·90·96·98·101·103·105·107·110·114·116·120] ➔ \n",
      "               >:[6·7·19·25·39·45·46·47·48·55·57·60·62·66·70·75·80·88·90·93·99·100·103·106·108·111·114·118]⚖[3·5·8·9·12·13·17·21·26·27·29·33·49·52·63·68·72·81·87·97·98·105·107·109·115·116·117·120] ➔ \n",
      "                    >:[4·7·8·18·26·30·43·48·53·64·66·74·79·81·84·90·109·111·112]⚖[9·20·28·33·39·52·56·80·82·83·85·89·91·95·100·107·114·118·120] ➔ >:+111 =:-29 <:-8) \n",
      "                    =:[7·9·11·15·21·22·23·32·42·45·50·52·53·54·60·77·78·87·103·105·109·111·114]⚖[1·3·8·10·14·16·24·26·30·31·35·36·37·41·44·62·67·72·80·91·93·99·118] ➔ >:-37 =:+89 <:-22) \n",
      "                    <:[2·6·8·11·13·16·21·22·33·34·37·40·42·44·45·48·49·51·52·56·57·58·61·64·66·67·77·84·86·87·94·101·105·111·113·114·115·119·120]⚖[7·9·18·23·25·28·31·32·35·41·43·46·50·53·55·59·65·68·70·72·75·76·78·80·81·83·85·89·92·100·102·103·104·106·108·109·116·117·118] ➔ >:+115 =:+97 <:-6)) \n",
      "               =:[8·9·14·15·16·19·20·23·27·37·44·47·48·50·59·60·61·69·78·80·82·83·84·89·90·94·97·99·100·106·108·117·118·119]⚖[1·2·4·13·18·21·30·32·33·35·36·38·39·40·43·52·56·57·62·65·67·71·79·81·85·88·93·96·101·103·104·105·111·116] ➔ \n",
      "                    >:[35·40·45·49·57·63·91·106]⚖[8·29·46·54·55·72·76·117] ➔ >:+106 =:-1 <:+117) \n",
      "                    =:[5·8·11·12·13·16·26·28·42·43·54·56·58·69·74·76·77·91·97·101·105·107·115·118]⚖[1·3·10·14·15·21·23·24·33·34·38·40·45·48·49·55·70·71·73·90·93·99·100·110] ➔ >:-34 =:+92 <:-11) \n",
      "                    <:[11·14·15·54·64·81·91]⚖[16·19·44·92·109·116·118] ➔ >:-16 =:+88 <:-15)) \n",
      "               <:[7·15·16·22·27·30·36·37·38·39·42·43·46·50·51·52·54·56·58·60·64·70·72·75·76·77·78·80·82·88·89·91·93·94·99·100·101·102·103·105]⚖[1·2·4·6·8·10·11·13·14·17·18·21·23·24·28·29·41·45·47·53·55·61·62·66·67·68·71·84·85·90·92·96·108·109·111·113·114·116·119·120] ➔ \n",
      "                    >:[10·14·26·31·41·51·62·63·93·105·114]⚖[9·13·55·61·79·90·92·94·115·116·120] ➔ >:+105 =:+82 <:-14) \n",
      "                    =:[10·15·18·25·26·34·35·39·40·42·43·46·47·53·58·59·61·62·66·67·70·79·80·89·96·99·101·110·120]⚖[3·6·8·9·11·13·23·28·29·32·50·60·69·74·76·78·82·84·85·87·92·93·95·102·108·109·111·113·119] ➔ >:+110 =:+107 <:-40) \n",
      "                    <:[7·11·13·23·27·40·41·45·46·53·55·56·58·62·71·76·83·88·95·101·109·114·115·117]⚖[2·8·20·28·29·34·42·47·50·54·59·64·66·68·69·74·75·79·91·93·94·102·103·106] ➔ >:+114 =:+96 <:-27))) \n",
      "          =:[5·6·10·13·19·20·23·26·28·37·41·46·48·52·53·57·58·61·62·64·66·67·68·70·71·72·73·78·83·94·96·99·105·107·108·109·117·118·120]⚖[1·3·7·9·12·18·21·25·27·29·30·31·32·34·38·42·43·44·47·49·54·55·56·60·75·76·79·81·85·86·88·92·98·100·102·103·104·106·115] ➔ \n",
      "               >:[3·6·12·16·21·22·24·25·27·31·33·46·66·67·76·79·84·87·89·92·94·110·112·120]⚖[15·18·23·26·38·39·42·44·45·47·52·53·56·57·62·64·71·90·93·96·99·105·108·118] ➔ \n",
      "                    >:[9·22·23·27·28·30·40·43·44·45·49·55·57·58·60·65·74·80·83·84·98·101·106·113·117·119]⚖[13·16·20·21·25·32·33·38·41·51·53·61·68·69·70·72·82·94·95·96·99·108·109·110·112·120] ➔ >:-38 =:-18 <:+120) \n",
      "                    =:[2·9·11·22·43·47·58·83·103·110·111·114]⚖[3·4·6·35·45·60·78·89·91·92·106·118] ➔ >:+83 =:+109 <:-9) \n",
      "                    <:[3·5·6·20·23·26·36·39·40·41·63·76·77·78·82·83·97·103·104·108]⚖[21·25·33·34·38·54·58·59·60·62·67·72·90·92·94·98·109·113·114·119] ➔ >:-21 =:-31 <:-3)) \n",
      "               =:[2·4·6·8·9·12·14·16·20·23·31·33·34·45·46·47·48·51·55·58·60·64·68·71·76·77·81·82·83·86·89·100·101·108·115·118·119]⚖[5·10·13·17·25·26·27·28·38·42·44·52·53·61·62·63·65·66·70·73·79·87·91·93·94·95·96·97·98·102·103·105·106·112·114·117·120] ➔ \n",
      "                    >:[3·10·12·25·28·65·69·80·81·90·101·108·109·112]⚖[19·23·34·39·40·60·63·76·77·94·100·102·114·119] ➔ >:+101 =:-17 <:+119) \n",
      "                    =:[7·17·19·20·25·28·34·37·38·46·48·51·54·57·60·62·70·71·76·90·93·95·97·98·105·118·120]⚖[1·2·6·9·27·29·35·45·50·53·58·65·69·73·79·83·84·85·87·88·91·94·96·111·115·117·119] ➔ >:-35 =:-36 <:+84) \n",
      "                    <:[28·51·60·61·95·99·103·108·115]⚖[31·38·62·64·69·91·94·96·97] ➔ >:+95 =:-2 <:+91)) \n",
      "               <:[2·6·14·17·21·23·25·26·27·29·31·43·44·49·59·64·71·74·88·90·95·100·103·104·106·116·119]⚖[5·7·8·16·18·19·28·34·37·38·45·48·57·67·73·76·77·78·86·89·91·93·97·98·99·113·114] ➔ \n",
      "                    >:[8·13·14·15·16·18·23·25·27·37·43·44·49·52·56·61·64·67·69·71·74·77·81·86·87·93·100·101·102·104·108·109·116]⚖[3·5·12·17·19·22·24·30·34·35·38·40·48·50·51·54·55·58·59·63·65·66·84·90·91·95·97·99·103·111·114·117·118] ➔ >:+104 =:-28 <:+103) \n",
      "                    =:[6·8·9·11·25·36·39·41·57·62·77·95·96·99·103·118]⚖[1·12·13·26·35·43·49·53·72·76·85·92·104·105·114·116] ➔ >:-13 =:+102 <:+85) \n",
      "                    <:[6·17·24·25·33·40·42·44·50·56·57·62·63·64·67·68·71·76·80·91·94·99·101·112·113·114·115·117·119·120]⚖[4·8·15·21·22·23·35·36·38·45·47·60·69·72·74·83·86·87·88·89·93·95·98·103·104·105·108·109·111·116] ➔ >:-23 =:-26 <:+98))) \n",
      "          <:[3·4·8·11·15·21·22·23·25·33·41·44·46·47·51·55·57·59·61·62·64·68·70·72·77·81·85·90·91·92·95·96·97·100·103·116·117·119·120]⚖[2·7·10·18·27·28·29·31·32·36·37·38·39·40·42·45·48·52·54·58·60·71·73·75·82·83·84·86·87·89·98·99·104·105·107·108·109·112·113] ➔ \n",
      "               >:[1·11·14·15·17·18·20·21·24·28·38·39·40·42·60·62·68·72·84·88·94·100·101·114·116·118]⚖[2·3·5·8·26·35·47·52·53·54·55·57·67·69·70·73·79·81·90·92·98·99·105·107·115·117] ➔ \n",
      "                    >:[2·11·31·67·89·118]⚖[20·37·41·74·90·100] ➔ >:0 =:+116 <:+100) \n",
      "                    =:[10·29·39·66·68·74·76]⚖[25·32·61·65·85·90·112] ➔ >:-32 =:-7 <:-10) \n",
      "                    <:[1·2·7·16·17·24·31·36·45·47·49·54·56·59·69·73·75·79·80·86·93·103·106·111·120]⚖[4·9·14·19·25·29·32·33·37·38·39·52·60·61·62·65·81·88·89·91·101·108·109·115·119] ➔ >:-39 =:+90 <:+81)) \n",
      "               =:[4·9·13·15·18·21·30·32·36·39·40·42·46·50·52·57·58·60·61·63·69·73·75·76·79·80·82·84·91·98·99·102·110·111·114·116]⚖[2·3·5·7·12·16·22·24·25·28·29·35·41·43·45·47·49·51·54·55·64·67·70·71·81·83·88·94·95·97·100·101·105·115·118·120] ➔ \n",
      "                    >:[3·11·14·24·27·46·49·53·55·56·60·68·75·79·90·114·116·119]⚖[4·9·12·13·18·41·47·61·65·80·88·92·98·99·102·106·109·117] ➔ >:-12 =:-5 <:-24) \n",
      "                    =:[1·2·10·11·13·15·20·23·27·29·33·34·39·46·54·58·61·69·74·78·79·82·83·84·90·91·99·100·101·105·111·118]⚖[3·4·5·6·7·19·21·22·26·28·30·31·35·37·41·45·47·49·67·72·76·77·80·86·95·103·104·108·109·114·117·120] ➔ >:-19 =:+93 <:-20) \n",
      "                    <:[2·4·5·7·30·35·41·44·50·61·63·66·67·71·73·84·94·95]⚖[1·9·19·21·25·48·49·57·68·70·79·88·97·100·104·107·109·117] ➔ >:+94 =:+118 <:-30)) \n",
      "               <:[3·16·17·19·23·25·27·34·37·39·41·43·46·48·51·54·55·56·62·67·71·75·81·82·85·87·95·109·111·112·113]⚖[2·6·9·12·15·18·24·30·38·40·42·57·60·65·68·69·73·76·84·86·89·92·94·99·100·103·104·107·110·116·119] ➔ \n",
      "                    >:[2·16·24·33·41·45·47·57·65·72·89·94·102·104·108·110·112·117]⚖[7·13·14·27·36·38·40·43·55·60·68·69·83·85·87·100·106·115] ➔ >:+112 =:+113 <:+87) \n",
      "                    =:[15·34·40·43·44·55·58·63·68·94·95·100·118]⚖[3·8·17·33·42·62·65·83·86·88·106·108·114] ➔ >:-33 =:-4 <:+108) \n",
      "                    <:[1·3·6·23·26·30·43·48·54·71·72·74·76·79·83·85·89·93·95·102·105·107·113]⚖[5·13·15·16·21·24·25·39·46·51·53·59·63·64·67·68·78·81·86·103·111·114·120] ➔ >:-25 =:+99 <:+86)))))\n"
     ]
    }
   ],
   "source": [
    "do(Puzzle(120, 5, {-1, 0, +1}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That works.\n",
    "\n",
    "Or, I could solve a puzzle with 243 possibilites (the maximum possible with 5 weighings): 242 lighter-only balls, plus the possibility that no ball is odd:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1·2·3·4·5·6·7·8·9·10·11·12·13·14·15·16·17·18·19·20·21·22·23·24·25·26·27·28·29·30·31·32·33·34·35·36·37·38·39·40·41·42·43·44·45·46·47·48·49·50·51·52·53·54·55·56·57·58·59·60·61·62·63·64·65·66·67·68·69·70·71·72·73·74·75·76·77·78·79·80·81]⚖[162·163·164·165·166·167·168·169·170·171·172·173·174·175·176·177·178·179·180·181·182·183·184·185·186·187·188·189·190·191·192·193·194·195·196·197·198·199·200·201·202·203·204·205·206·207·208·209·210·211·212·213·214·215·216·217·218·219·220·221·222·223·224·225·226·227·228·229·230·231·232·233·234·235·236·237·238·239·240·241·242] ➔ \n",
      "     >:[2·3·5·8·16·17·20·21·22·31·34·37·38·43·45·47·48·49·51·52·53·58·61·67·71·72·73·74·76·79·80·84·85·91·95·96·99·102·115·120·121·123·125·127·129·132·135·139·140·146·148·155·159·161·164·171·172·177·181·182·184·185·188·189·190·195·204·206·207·211·213·214·215·220·224·225·230·231·234·235·240]⚖[1·9·10·11·12·14·19·24·26·27·32·33·36·46·54·55·57·64·66·68·69·75·78·81·82·83·86·87·88·90·93·98·101·103·105·106·109·110·113·114·117·118·119·122·128·130·133·141·142·143·144·145·152·153·163·165·167·175·176·178·179·180·187·191·192·193·197·199·201·202·208·210·216·219·222·226·227·233·239·241·242] ➔ \n",
      "          >:[2·3·4·18·20·23·26·27·35·36·37·39·44·49·50·58·60·62·66·68·73·75·79·81·82·83·89·90·97·101·103·106·108·116·124·128·132·135·136·137·138·141·144·149·154·155·160·165·174·178·180·182·187·192·193·197·198·206·207·209·211·217·218·221·232·237·238·239·241]⚖[1·5·9·10·11·12·13·16·17·19·22·29·30·41·45·46·47·56·65·70·74·77·80·84·86·88·96·102·109·114·115·119·120·125·126·133·134·143·148·151·153·157·161·162·163·167·169·172·181·183·188·190·191·194·196·199·201·203·205·210·213·214·222·224·227·228·231·240·242] ➔ \n",
      "               >:[1·8·14·17·18·20·22·26·37·42·45·48·49·50·55·58·64·67·69·70·71·72·77·78·82·83·86·87·93·96·98·102·104·105·110·117·119·120·126·132·133·135·138·140·142·143·147·149·151·155·156·158·160·166·167·169·171·173·175·178·182·184·185·191·192·196·202·216·220·221·223·226·227·235·236·238·241]⚖[3·4·5·7·9·12·13·15·16·19·27·28·29·31·34·35·38·39·43·47·51·56·63·65·68·79·84·89·90·91·94·97·99·103·108·111·115·116·122·127·129·130·134·139·141·145·146·150·152·159·161·163·164·165·170·172·174·177·179·181·186·193·194·198·199·200·203·206·207·209·210·212·215·219·228·234·240] ➔ \n",
      "                    >:[7·24·27·29·37·39·47·53·54·59·64·76·93·95·116·122·133·142·146·153·155·158·177·210·213·220]⚖[17·31·36·40·43·58·73·88·101·104·107·112·118·131·136·145·151·156·159·163·168·175·179·200·202·230] ➔ >:-163 =:-199 <:-210) \n",
      "                    =:[3·8·10·17·20·21·22·25·28·43·45·49·51·54·79·89·101·112·117·119·120·128·131·134·152·167·170·177·182·193·196·200·203·205·206·210·214·219·222·223·230·237·240·241]⚖[6·11·18·27·55·56·61·66·70·71·74·76·80·91·96·99·102·106·110·113·118·123·127·130·133·141·142·155·157·160·166·183·188·201·204·208·215·217·224·225·228·231·233·235] ➔ >:-201 =:-242 <:-222) \n",
      "                    <:[14·20·36·37·46·66·82·114·128·132·139·144·167·189·194·206·208·212·217·220·221·226·231·232]⚖[10·11·13·16·40·41·53·69·74·75·76·90·98·100·124·135·146·161·170·172·184·198·202·227] ➔ >:-227 =:-191 <:-167)) \n",
      "               =:[2·4·14·20·24·30·36·37·43·45·48·50·51·52·56·58·59·61·68·69·70·71·74·75·78·85·90·94·103·105·106·116·121·122·130·133·134·135·136·141·145·146·150·152·159·164·172·175·176·177·181·182·188·192·200·201·205·208·215·227·241]⚖[5·6·10·11·12·17·21·23·25·31·38·42·47·53·62·66·72·79·80·82·83·86·92·93·96·111·113·115·117·118·119·120·126·129·131·153·154·155·157·161·162·165·168·170·173·179·183·186·187·193·199·214·216·221·225·226·232·234·237·238·240] ➔ \n",
      "                    >:[2·6·15·54·60·80·94·97·99·103·104·108·109·118·119·139·145·149·154·162·164·169·178·190·211·223·226]⚖[7·16·17·22·26·50·56·61·73·77·85·89·96·100·105·107·113·122·148·161·166·179·187·202·213·235·239] ➔ >:-179 =:-216 <:-226) \n",
      "                    =:[5·8·43·50·87·107·122·123·124·137·157·165·173·179·185·186·190·194·197·214·219·223·224·232]⚖[18·21·39·40·48·52·70·74·92·94·97·100·102·106·131·138·145·156·161·182·183·191·200·202] ➔ >:-202 =:-233 <:-219) \n",
      "                    <:[5·12·28·32·45·51·59·60·68·69·74·75·78·87·90·92·94·96·101·117·120·122·127·145·152·153·162·167·171·175·177·190·213·223·227]⚖[4·23·33·38·47·55·62·88·93·97·102·113·118·130·140·143·150·157·159·160·168·172·181·184·185·188·192·204·208·209·211·215·224·225·242] ➔ >:-208 =:-176 <:-175)) \n",
      "               <:[1·3·7·13·17·20·23·34·35·41·46·48·49·64·66·70·71·77·84·87·88·99·101·113·133·134·148·152·153·162·163·168·175·180·185·187·196·197·210·217·222·223·226·227·238·240]⚖[5·10·16·22·26·50·54·58·72·73·74·83·89·91·97·112·119·121·124·125·128·129·130·135·144·146·147·158·160·164·165·167·170·172·173·174·177·178·184·192·200·213·218·229·234·242] ➔ \n",
      "                    >:[16·17·42·81·89·112·115·130·144·166·178·185·201·219·234·235]⚖[1·26·53·56·78·91·106·113·122·136·145·148·152·165·214·216] ➔ >:-165 =:-192 <:-178) \n",
      "                    =:[23·33·37·42·51·68·82·85·108·111·134·147·152·158·165·183·184·191·213·226·235·239·242]⚖[5·13·25·57·78·102·106·107·118·151·162·173·178·186·187·196·197·208·227·229·233·237·241] ➔ >:-241 =:-193 <:-239) \n",
      "                    <:[16·19·25·48·51·63·68·74·105·110·120·128·131·133·147·148·157·164·189·193·196·197·210·217·236·242]⚖[2·14·17·24·33·37·70·80·84·92·101·104·117·121·127·132·144·159·161·170·180·209·211·216·219·238] ➔ >:-180 =:-187 <:-197))) \n",
      "          =:[4·5·6·8·9·10·11·12·13·14·17·27·41·44·46·48·49·54·55·60·61·72·73·74·75·76·79·80·82·87·89·94·103·108·113·117·120·124·125·130·131·133·137·139·140·146·147·148·149·152·154·156·157·160·161·166·168·171·183·185·186·188·189·194·197·199·201·207·208·209·212·221·225·231·237·240·241·242]⚖[3·7·18·19·22·24·25·26·32·33·35·36·37·47·51·56·58·62·65·71·77·81·88·90·92·93·95·96·98·101·102·104·106·109·110·111·115·118·119·123·127·134·135·142·143·150·153·162·163·164·165·173·174·175·178·179·180·184·190·204·205·211·213·214·216·218·219·220·222·223·226·227·228·229·232·234·235·239] ➔ \n",
      "               >:[1·4·5·7·9·11·12·14·17·18·20·28·29·33·34·35·39·41·42·43·45·49·51·53·59·62·64·69·74·78·79·84·89·90·94·100·104·111·115·128·130·134·136·137·138·139·146·149·152·155·162·165·166·167·172·173·181·184·187·189·191·193·195·205·207·209·212·214·224·227·231·233·234·236·242]⚖[19·22·24·30·32·40·44·54·56·60·61·63·65·66·68·70·76·81·86·87·92·93·95·98·102·103·107·114·117·118·119·120·121·124·125·126·127·131·132·133·135·140·141·142·143·144·147·150·151·154·157·161·163·164·176·178·179·182·190·194·197·200·210·213·215·219·221·223·225·229·232·237·239·240·241] ➔ \n",
      "                    >:[11·30·37·41·51·53·59·71·74·85·88·115·122·124·128·136·144·149·157·162·167·180·184·193·201·217·223·225·235]⚖[3·7·9·12·28·42·45·46·52·56·62·65·67·84·93·95·101·120·123·139·166·183·186·189·191·192·205·229·230] ➔ >:-229 =:-232 <:-223) \n",
      "                    =:[5·8·9·16·17·23·27·34·40·47·48·72·76·84·91·94·100·104·111·113·131·132·144·150·152·162·167·174·175·176·178·181·191·198·204·212·219·220·224·225·231·235·238·240]⚖[3·7·12·18·24·28·37·42·43·45·54·66·74·87·90·106·107·108·112·119·122·128·130·135·143·151·153·173·180·183·187·195·200·207·211·215·216·217·218·221·223·226·239·242] ➔ >:-218 =:-228 <:-174) \n",
      "                    <:[3·11·13·26·34·35·48·53·55·59·60·78·87·88·102·104·114·121·126·131·139·151·154·162·167·172·175·178·188·191·212·213·214·218·229·232·239]⚖[5·7·12·18·23·37·45·46·50·56·62·65·66·84·90·96·105·123·124·129·136·144·147·150·152·159·182·186·198·201·205·215·216·217·228·234·236] ➔ >:-205 =:-173 <:-162)) \n",
      "               =:[6·7·9·11·22·29·33·34·35·36·40·45·48·50·54·57·59·60·62·71·75·76·77·78·86·97·101·108·118·120·123·125·128·133·134·139·145·147·148·151·155·160·163·166·167·170·171·177·183·185·188·189·192·193·197·198·200·201·209·210·213·214·221·223·226·229·232·234]⚖[1·3·4·12·18·19·20·25·27·30·31·41·46·49·63·65·68·69·72·73·82·89·92·93·94·98·99·100·110·111·112·113·114·115·116·122·126·131·132·140·143·144·146·149·150·152·156·157·159·162·172·176·179·184·187·190·199·203·206·207·208·215·217·219·220·227·236·237] ➔ \n",
      "                    >:[24·27·29·37·39·41·50·65·74·76·83·86·91·93·99·120·122·126·129·134·140·141·156·172·190·191·193·197·199·217·224·226·241]⚖[1·8·10·12·13·31·32·33·45·47·60·67·70·71·73·75·114·115·119·121·128·132·135·136·143·145·148·154·171·185·186·203·240] ➔ >:-203 =:-236 <:-217) \n",
      "                    =:[4·15·18·38·57·59·66·69·74·84·101·105·111·133·139·147·172·196·199·207·216]⚖[16·25·30·33·42·43·49·54·81·103·128·163·176·182·203·204·213·224·228·229·238] ➔ >:-238 =:-169 <:-196) \n",
      "                    <:[9·17·27·34·41·44·60·67·117·118·122·166·198·201·209·225]⚖[20·25·31·35·107·121·123·133·148·184·200·207·210·217·219·237] ➔ >:-200 =:-170 <:-198)) \n",
      "               <:[9·10·12·16·20·28·30·33·35·36·37·40·41·44·45·49·56·62·64·66·67·72·73·78·85·86·93·97·99·102·103·105·108·110·117·118·138·141·146·149·152·155·157·162·165·169·171·173·175·178·179·180·182·183·184·185·186·195·196·201·209·210·215·216·223·229·235·240·242]⚖[7·14·15·17·18·22·25·31·34·42·43·47·55·59·61·68·70·71·75·76·77·81·89·90·91·104·106·107·109·113·115·119·120·124·127·128·131·135·143·144·148·153·154·158·160·163·164·166·168·170·172·174·190·192·198·202·203·204·208·217·224·225·226·232·233·236·237·238·239] ➔ \n",
      "                    >:[16·20·24·31·34·44·45·48·51·52·78·82·85·108·109·136·143·164·166·169·179·192·212·214·216·217·227·228·238·241·242]⚖[5·12·55·67·71·75·77·89·91·100·111·116·126·132·137·138·153·159·160·168·186·188·195·197·211·215·221·225·230·231·235] ➔ >:-168 =:-237 <:-166) \n",
      "                    =:[4·7·26·30·58·62·63·73·125·129·154·165·170·183·193·195·205·212·217·231·237]⚖[2·8·34·40·46·71·83·132·162·169·172·174·188·194·197·200·204·224·235·236·239] ➔ >:-194 =:-221 <:-212) \n",
      "                    <:[8·15·18·24·53·66·73·95·109·110·125·130·136·150·165·176·182·183·191·200·230·232]⚖[4·27·31·44·63·90·94·101·128·131·138·158·173·174·197·207·209·222·224·225·227·233] ➔ >:-209 =:-186 <:-183))) \n",
      "          <:[4·7·9·10·13·16·18·21·23·24·26·27·30·32·35·44·45·47·60·62·63·77·78·79·82·83·85·87·91·93·96·100·107·108·112·113·114·115·118·139·140·141·146·151·155·156·157·158·164·166·167·168·171·173·178·182·185·189·196·197·200·204·208·209·210·214·215·217·219·225·229·237]⚖[5·17·19·22·25·36·38·39·41·46·48·50·64·68·70·71·72·74·76·80·81·86·88·92·101·102·106·109·110·111·121·124·126·127·131·134·135·142·143·145·148·149·150·153·159·161·162·165·169·177·179·181·183·184·186·188·190·193·195·202·203·205·207·216·218·227·228·234·235·236·241·242] ➔ \n",
      "               >:[3·5·6·7·8·9·11·18·21·22·36·39·43·49·50·51·53·62·80·81·86·93·100·104·105·111·118·120·121·125·144·145·172·197·199·204·206·207·223·234·235·238]⚖[13·14·16·20·23·24·38·40·44·60·67·69·70·79·90·91·96·98·108·109·114·119·131·135·140·142·143·150·151·155·159·176·177·178·180·184·186·188·203·210·237·241] ➔ \n",
      "                    >:[4·9·27·29·41·48·53·57·59·76·80·94·99·100·135·139·141·145·146·150·162·166·172·177·182·185·192·195·214·228·233]⚖[1·25·37·40·54·62·65·66·82·93·111·114·125·128·131·133·140·142·158·171·174·178·179·180·184·208·213·215·218·225·231] ➔ >:-184 =:-188 <:-177) \n",
      "                    =:[2·25·28·33·45·47·60·61·73·86·101·120·125·140·144·146·155·159·161·165·171·172·181·191·192·215·219·234·236·240]⚖[13·14·17·18·19·29·34·46·62·67·80·81·90·91·99·115·117·128·142·174·176·190·194·197·210·223·231·232·235·237] ➔ >:-190 =:-195 <:-181) \n",
      "                    <:[50·58·60·67·85·96·103·133·134·142·153·168·174·187·189·197·202·205·210·218·234·242]⚖[10·13·28·35·45·57·62·63·68·70·87·92·117·140·179·198·201·207·212·221·223·225] ➔ >:-207 =:-235 <:-234)) \n",
      "               =:[2·4·9·13·16·18·25·27·28·34·40·54·58·60·63·65·70·75·76·81·84·85·88·93·97·99·101·103·104·105·117·121·124·144·149·156·158·166·174·178·182·186·193·198·201·205·206·213·214·217·218·222·224·234·238]⚖[1·5·8·15·20·21·22·26·31·32·35·47·49·55·56·61·62·69·79·82·83·86·94·96·98·111·114·116·119·123·125·129·130·136·139·141·145·150·152·153·155·157·172·175·180·184·188·191·194·208·229·230·237·239·240] ➔ \n",
      "                    >:[1·15·64·82·96·101·105·135·143·145·147·157·160·172·176·182·189·192·194·198·227·242]⚖[12·20·21·36·42·48·62·65·75·84·87·95·99·103·115·126·142·148·164·183·230·235] ➔ >:-230 =:-240 <:-172) \n",
      "                    =:[3·11·12·14·16·23·62·63·71·94·97·99·101·127·138·145·150·151·155·156·167·168·170·180·187·195·204·208·218·222·224·225·229·231·234·238]⚖[6·9·22·24·28·29·30·39·40·47·53·55·59·60·70·72·87·107·120·129·134·135·143·144·146·157·179·182·184·185·206·215·220·227·237·242] ➔ >:-220 =:-211 <:-231) \n",
      "                    <:[8·11·14·31·35·46·50·51·52·61·64·82·103·121·129·132·145·146·147·154·157·173·183·189·194·199·206·214·216·225·230·233]⚖[25·29·33·54·66·70·78·79·93·96·99·111·114·120·125·128·134·139·142·148·152·160·166·167·186·197·200·213·228·229·239·241] ➔ >:-213 =:-224 <:-206)) \n",
      "               <:[1·9·13·26·27·28·29·35·39·45·47·49·59·69·73·74·75·82·83·84·85·91·95·96·98·100·101·104·108·109·111·115·123·126·127·129·134·136·137·138·139·140·151·153·158·160·166·167·175·180·186·195·199·203·204·207·215·217·218·223·225·227·231·236·238·239·240·241]⚖[3·4·6·11·12·17·18·20·21·23·30·37·38·42·50·51·56·60·62·63·67·70·72·80·90·97·105·107·110·114·118·120·121·124·128·132·146·147·149·150·154·155·165·170·171·173·174·179·182·183·184·190·191·194·200·206·208·209·211·213·214·216·219·222·226·229·234·235] ➔ \n",
      "                    >:[6·9·21·40·48·57·78·79·105·106·109·124·132·141·145·154·156·166·167·171·177·178·188·190·206·216]⚖[17·20·24·29·31·32·70·77·82·85·101·115·119·131·136·137·140·152·173·182·208·210·213·220·230·237] ➔ >:-182 =:-214 <:-171) \n",
      "                    =:[13·18·26·31·33·35·88·106·122·129·139·142·165·176·177·182·185·193·194·214·229·239]⚖[23·37·39·45·51·53·54·73·80·90·104·119·124·126·132·134·161·168·189·203·219·221] ➔ >:-189 =:-164 <:-185) \n",
      "                    <:[7·23·48·50·55·63·79·86·97·100·106·109·110·111·114·140·147·156·178·191·206·207·211·223·225·236·241]⚖[1·3·12·16·35·36·43·61·77·81·85·99·102·112·122·123·139·145·176·177·179·189·204·221·222·224·234] ➔ >:-204 =:-215 <:-225)))) \n",
      "     =:[14·15·17·18·20·21·28·37·38·42·50·51·52·54·55·56·57·58·60·62·76·77·78·84·86·87·89·93·100·104·107·109·113·115·122·123·125·126·128·131·139·141·142·143·144·145·147·156·158·161·166·167·168·173·184·191·195·198·200·202·203·209·210·216·222·227·232·233·237·238·239·240·241·242]⚖[1·3·4·9·11·12·22·23·24·25·27·30·33·36·39·45·63·64·66·67·68·69·70·71·79·83·90·91·92·94·95·97·98·99·102·103·105·108·110·112·114·116·118·119·124·133·134·136·137·146·151·157·162·163·169·170·175·178·181·182·183·187·189·190·201·206·211·213·215·221·226·231·234·235] ➔ \n",
      "          >:[2·3·4·15·29·30·33·35·37·46·48·58·63·72·78·80·87·88·90·99·101·103·106·107·115·119·120·127·129·133·134·136·137·143·145·148·151·155·163·164·165·168·170·177·180·182·189·191·198·205·220·225·227·229·232·234·236·241·242]⚖[20·22·26·28·31·32·36·38·42·44·49·52·53·56·64·74·79·82·83·84·86·91·92·93·95·98·104·112·114·117·118·128·131·135·138·139·150·157·159·160·169·171·174·175·179·185·192·201·208·211·214·216·217·219·221·228·238·239·240] ➔ \n",
      "               >:[14·20·24·28·40·42·52·53·57·64·65·69·70·79·83·89·95·96·97·99·109·114·115·128·131·134·138·142·143·145·147·149·150·151·160·167·171·176·178·184·185·187·188·190·196·209·222·227·228·229·230·238]⚖[5·10·17·26·27·38·44·46·50·51·55·56·63·67·68·78·82·93·98·100·104·110·112·117·118·120·125·127·132·137·144·146·152·154·156·159·161·162·164·166·172·177·182·195·197·198·211·219·220·231·235·242] ➔ \n",
      "                    >:[21·57·74·118·127·150·153·191·201·217·226]⚖[7·30·75·79·93·112·120·144·193·219·230] ➔ >:-112 =:-98 <:-118) \n",
      "                    =:[7·10·13·21·22·32·40·42·49·72·74·76·82·86·92·102·111·114·119·120·124·126·129·136·150·154·159·165·167·169·170·172·176·184·188·196·198·204·218·220·224·227·229·234·236·237·242]⚖[3·4·5·14·17·19·26·29·33·34·38·44·50·52·56·58·62·63·68·69·79·81·88·89·91·107·110·115·117·127·134·138·139·143·149·152·161·173·175·183·207·208·209·212·216·217·240] ➔ >:-91 =:-157 <:-92) \n",
      "                    <:[3·114·127·134·138·172·180·187·195]⚖[56·95·105·188·198·200·204·224·225] ➔ >:-95 =:-83 <:-114)) \n",
      "               =:[18·20·21·29·56·73·74·82·89·93·97·100·101·103·110·119·130·134·146·151·157·163·174·178·179·180·181·189·196·204·206·208·211·213·225·231·241]⚖[8·10·16·17·27·32·44·49·54·59·61·72·80·81·94·96·102·106·115·116·117·128·137·139·153·164·173·176·177·194·197·205·212·216·222·230·237] ➔ \n",
      "                    >:[12·14·19·20·24·26·28·35·49·50·61·70·78·85·97·108·110·111·116·120·123·126·133·134·164·166·176·179·181·200·214·215·219·220·221·226·232·235·242]⚖[9·15·29·30·41·45·59·60·63·64·66·68·81·82·86·88·92·99·101·102·103·106·113·135·138·151·154·177·180·183·184·189·195·224·225·228·231·234·239] ➔ >:-102 =:-94 <:-116) \n",
      "                    =:[6·9·10·21·36·38·47·52·55·58·66·69·70·101·108·114·141·142·202·211·213·218·224·228·233·240·241]⚖[12·14·20·26·32·34·39·59·73·79·87·90·103·105·106·122·125·126·127·129·144·151·167·173·196·223·234] ➔ >:-105 =:-124 <:-108) \n",
      "                    <:[8·11·15·24·30·39·47·52·62·74·79·81·91·93·97·102·104·119·120·124·149·155·158·164·167·170·186·198·209·217·229]⚖[2·9·10·18·28·31·32·38·40·41·48·61·71·73·90·94·125·131·143·145·146·176·193·194·205·213·219·223·233·237·240] ➔ >:-146 =:-110 <:-97)) \n",
      "               <:[6·14·16·24·29·33·35·41·49·59·64·71·74·82·85·91·92·94·95·96·103·114·115·126·129·131·134·137·139·141·143·152·156·158·160·162·163·166·174·175·180·186·187·191·196·197·210·212·220·222·229·234·235·237·238·240]⚖[1·3·10·17·21·30·31·36·39·45·48·51·56·58·60·61·66·67·72·73·77·83·86·93·97·99·104·109·110·112·116·117·118·119·123·124·125·128·132·136·144·148·159·167·168·171·172·181·185·207·208·217·223·230·232·239] ➔ \n",
      "                    >:[3·11·12·13·17·19·24·30·36·37·42·46·47·49·57·71·72·96·99·104·106·109·124·126·132·142·157·163·172·198·201·203·206·209·217·218·219·220·221·229·234·236]⚖[4·5·9·18·26·29·31·40·43·58·60·63·67·74·95·110·118·127·130·131·133·134·136·145·148·154·155·156·158·159·161·162·164·165·166·168·182·187·208·213·214·226] ➔ >:-136 =:-119 <:-99) \n",
      "                    =:[2·6·7·12·13·15·17·18·31·36·39·41·46·49·59·62·63·69·79·85·87·88·100·109·117·133·137·145·146·147·153·161·163·165·166·183·184·185·188·193·204·206·213·216·231·238·242]⚖[14·26·34·44·55·57·58·65·68·75·82·84·86·95·101·102·103·104·112·121·122·123·127·129·136·144·150·151·157·167·168·173·174·181·187·194·197·207·209·211·220·226·233·234·237·240·241] ➔ >:-151 =:-90 <:-133) \n",
      "                    <:[24·25·42·45·61·64·67·73·75·85·88·110·114·118·126·132·137·146·149·151·158·162·163·173·178·189·198·204·216·217·225]⚖[1·2·11·13·28·32·51·52·59·78·83·94·97·102·105·107·119·127·134·154·161·165·185·202·211·213·220·222·229·231·233] ➔ >:-134 =:-103 <:-137))) \n",
      "          =:[2·4·5·6·8·9·10·12·14·15·18·19·21·22·26·27·31·32·36·42·44·45·50·53·56·63·67·68·73·74·75·78·79·81·82·86·93·96·97·98·105·109·111·115·118·124·128·137·140·142·145·148·153·154·155·157·159·162·166·170·175·176·180·183·184·187·192·195·199·209·214·217·219·221·222·223·231·233·235·238]⚖[11·13·20·25·33·35·37·39·40·43·46·47·49·52·54·55·57·58·59·60·61·62·64·65·71·76·80·83·84·87·88·89·90·95·100·106·107·110·116·117·120·125·127·131·132·133·135·136·138·139·144·150·151·158·164·165·167·168·169·171·178·181·189·191·193·197·200·201·206·207·208·215·216·225·226·227·230·239·240·241] ➔ \n",
      "               >:[1·11·13·16·23·28·31·38·40·43·44·45·47·48·49·50·58·65·66·73·76·79·81·83·85·88·96·97·99·100·101·105·107·108·116·118·124·130·133·134·136·138·144·145·147·150·159·161·166·168·169·170·175·184·189·192·193·194·195·200·202·216·217·219·221·222·223·225·228·229·235·238·240·241]⚖[3·5·7·10·15·19·20·24·26·27·29·37·39·41·42·52·53·56·60·64·67·69·75·78·80·82·90·92·98·103·106·110·111·112·113·114·115·119·120·122·125·126·131·132·137·140·142·152·156·157·158·162·163·171·176·178·182·187·188·190·196·198·205·208·210·215·218·220·224·226·227·230·237·239] ➔ \n",
      "                    >:[23·51·60·66·80·103·105·112·114·132·142·159·176·179·201·217·223·233·234·236]⚖[14·48·79·88·97·101·102·104·120·124·137·144·169·177·200·215·218·225·232·239] ➔ >:-120 =:-106 <:-132) \n",
      "                    =:[1·7·12·14·20·34·35·36·49·51·57·76·92·93·95·120·122·135·144·146·151·157·159·162·169·174·180·189·190·206·223·225·234·239·240]⚖[3·13·17·23·27·28·45·50·56·65·66·68·78·79·84·87·112·114·117·118·133·134·138·141·149·156·163·172·185·191·192·199·204·205·218] ➔ >:-117 =:-127 <:-135) \n",
      "                    <:[2·12·21·31·33·34·70·81·86·88·101·105·109·110·115·117·123·124·125·129·131·133·149·156·159·165·195·203·211·215·216·220·225·237·239·241·242]⚖[10·16·23·35·45·52·56·57·61·64·68·69·72·98·108·119·120·134·137·138·140·143·144·155·157·161·164·168·179·182·185·187·190·191·204·224·228] ➔ >:-138 =:-150 <:-88)) \n",
      "               =:[4·7·11·12·16·25·26·33·43·49·50·55·56·58·67·70·71·73·74·92·93·95·97·98·100·101·105·107·117·130·140·145·147·148·149·153·154·156·159·173·174·178·187·188·208·212·214·216·230·234·238·239]⚖[1·3·10·19·23·36·37·44·45·47·52·53·54·57·59·62·63·65·66·76·77·81·85·90·91·103·119·127·128·129·134·142·151·152·158·161·163·166·179·182·192·193·194·200·201·205·218·231·232·235·237·241] ➔ \n",
      "                    >:[40·55·68·73·75·77·85·88·94·95·98·110·121·135·159·186·197·214·229·238]⚖[32·42·43·57·62·86·87·113·117·133·152·170·173·184·192·193·196·205·211·215] ➔ >:-152 =:-129 <:-85) \n",
      "                    =:[9·11·27·29·31·36·38·43·44·45·46·48·53·66·70·71·88·93·99·104·106·113·114·118·120·121·124·126·129·131·137·148·151·155·161·162·165·166·167·170·171·173·177·181·182·189·190·192·198·207·212·218·222·234·238·240]⚖[2·3·7·8·10·12·13·14·19·21·22·23·34·55·60·64·69·73·74·81·82·83·89·90·91·94·98·101·107·115·123·135·136·140·141·143·149·156·160·163·164·168·180·186·187·191·196·199·202·208·220·224·226·228·229·242] ➔ >:-160 =:0 <:-121) \n",
      "                    <:[8·9·13·20·26·28·29·34·38·48·51·54·58·78·81·88·92·99·105·111·112·116·120·122·128·130·131·136·146·147·153·160·165·168·170·178·188·189·193·202·205·208·212·213·214·222·228·231·239·241]⚖[2·5·7·10·31·33·52·61·62·63·65·66·68·75·79·82·83·87·89·95·98·100·102·107·114·119·126·127·149·158·161·169·174·176·184·190·201·206·207·209·210·216·219·220·225·226·233·234·240·242] ➔ >:-149 =:-101 <:-130)) \n",
      "               <:[1·8·15·17·21·23·28·30·34·36·42·46·64·70·76·79·82·89·93·102·107·112·114·115·116·117·133·138·141·146·148·157·159·161·165·176·185·186·190·194·201·203·204·208·211·212·214·216·220·224·228·230·233·237·240]⚖[2·10·14·16·19·22·25·31·40·43·47·56·59·62·67·68·69·71·72·73·77·83·85·87·88·90·91·96·98·100·103·104·105·108·119·121·128·129·144·150·151·153·154·160·162·173·174·182·198·199·202·218·221·223·234] ➔ \n",
      "                    >:[4·11·28·52·55·57·60·89·96·98·123·152·176·178·183·198·220·226]⚖[3·8·21·22·29·39·42·54·61·80·84·107·132·148·154·164·231·233] ➔ >:-154 =:-153 <:-96) \n",
      "                    =:[28·31·39·47·56·61·75·98·114·140·141·153·158·164·170·173·184·191·193·225·233·236·237·238·239·241]⚖[5·9·21·24·33·43·45·48·73·80·81·89·95·104·111·113·123·132·142·149·171·188·209·220·230·232] ➔ >:-111 =:-155 <:-140) \n",
      "                    <:[3·4·5·14·17·18·22·25·40·42·52·57·65·66·75·76·78·82·92·94·99·110·126·127·128·132·134·145·146·150·153·157·158·162·166·180·206·210·211·225·227·240]⚖[1·2·8·16·19·23·30·33·41·47·55·56·61·64·70·73·85·95·96·106·107·125·129·142·148·151·164·171·173·176·182·183·187·193·195·198·200·208·215·218·230·239] ➔ >:-148 =:-159 <:-82))) \n",
      "          <:[5·8·9·15·16·27·28·32·43·46·50·54·55·59·61·63·65·74·75·78·79·81·89·90·91·96·100·108·115·117·122·123·124·125·127·130·131·132·143·146·148·156·159·160·162·164·169·171·173·176·179·181·182·196·198·200·201·202·208·210·215·218·219·222·223·224·234·239·242]⚖[1·3·4·7·12·22·29·33·35·36·38·39·42·48·52·57·58·64·67·68·72·80·83·84·85·86·87·88·93·94·97·98·99·102·107·111·113·121·126·133·137·141·144·153·163·167·170·172·184·185·187·188·192·193·195·199·203·205·206·207·209·211·212·221·225·231·232·236·237] ➔ \n",
      "               >:[4·5·11·12·13·14·17·24·31·36·46·47·51·52·55·60·64·82·87·90·92·97·103·104·105·107·116·119·120·122·125·128·132·134·137·139·141·146·149·151·160·168·169·176·183·188·193·195·202·204·206·209·220·224·226·230·232·236·240·241]⚖[6·8·9·10·22·23·25·27·28·29·34·35·37·38·40·45·49·57·59·88·93·99·100·102·106·113·114·118·121·126·140·153·154·159·162·165·166·170·171·172·173·174·175·177·178·179·186·187·200·201·203·210·214·217·219·223·227·229·231·234] ➔ \n",
      "                    >:[5·11·12·24·26·43·48·60·63·66·69·73·79·82·85·87·93·98·101·114·129·131·132·139·142·162·163·164·165·168·172·188·212·220·226·228·232·234]⚖[2·8·9·16·20·25·30·36·38·39·41·49·58·68·70·71·76·80·95·105·106·109·110·111·120·126·151·161·166·174·179·183·184·191·201·210·236·238] ➔ >:-126 =:-113 <:-93) \n",
      "                    =:[9·43·54·81·97·106·130·144·145·147·148·149·177·197·199·201·202·209·217·236·241]⚖[1·3·24·29·32·36·37·44·70·72·79·83·86·95·133·139·163·179·200·210·211] ➔ >:-86 =:-84 <:-144) \n",
      "                    <:[5·17·22·23·31·34·43·45·46·51·63·64·66·70·74·81·87·90·106·112·114·116·121·124·129·134·137·144·145·155·164·170·171·176·179·180·184·185·188·203·206·209·214·216·219·239·242]⚖[3·4·7·13·21·30·32·36·39·40·48·56·59·60·73·77·79·91·93·96·105·107·126·132·136·147·149·151·153·154·156·161·165·174·177·181·183·189·192·205·207·211·212·220·235·236·237] ➔ >:-107 =:-141 <:-87)) \n",
      "               =:[1·4·7·10·13·21·22·23·27·29·35·38·39·40·42·44·49·50·61·62·63·64·67·72·81·82·84·85·87·88·90·112·114·117·118·121·125·133·139·144·147·149·157·159·161·168·174·176·177·178·181·183·187·190·191·192·197·198·199·201·203·209·212·220·225·226·235]⚖[2·6·8·12·14·15·17·20·25·26·32·36·43·45·46·51·56·58·65·69·73·74·75·76·77·83·94·98·106·109·111·122·132·135·136·138·140·142·143·146·148·151·152·154·156·158·164·166·171·175·180·185·188·193·194·204·205·208·216·217·218·228·231·233·238·240·242] ➔ \n",
      "                    >:[19·37·60·66·67·86·96·102·106·118·122·123·138·142·144·147·153·168·174·181·185·194·199·205·211·213·221·227·229]⚖[22·24·26·31·49·53·56·70·73·83·101·134·140·145·148·156·158·159·173·176·180·182·186·197·204·214·232·233·240] ➔ >:-158 =:-109 <:-142) \n",
      "                    =:[9·28·37·38·49·58·59·70·84·90·94·97·103·113·119·120·135·136·137·139·145·148·149·155·158·185·194·199·219·220·227·229·231]⚖[1·22·23·29·39·47·51·53·54·67·71·82·89·92·99·101·104·153·156·160·161·165·171·172·175·197·214·215·225·228·232·233·235] ➔ >:-104 =:-128 <:-145) \n",
      "                    <:[50·70·84·130·161·182·197·238]⚖[39·42·44·54·109·139·230·231] ➔ >:-139 =:-147 <:-161)) \n",
      "               <:[7·10·11·21·38·43·52·61·64·65·66·72·88·96·97·114·115·118·120·122·124·126·130·131·147·150·182·185·189·193·196·199·204·215·224·235·239]⚖[2·6·13·20·25·29·36·40·41·44·45·68·73·74·76·79·91·109·123·125·127·135·137·139·143·160·164·170·174·177·178·184·202·231·233·237·242] ➔ \n",
      "                    >:[2·5·10·14·18·21·25·28·37·44·47·56·65·68·75·79·82·86·92·95·101·103·110·117·123·127·133·135·142·144·145·151·165·182·184·189·199·201·205·208·220·224·235·236]⚖[16·20·22·27·33·34·39·41·50·60·61·66·72·81·93·98·111·119·121·131·139·141·143·148·150·160·161·164·173·178·187·193·195·207·209·210·211·213·228·229·230·232·238·239] ➔ >:-143 =:-125 <:-123) \n",
      "                    =:[6·38·51·54·57·63·64·69·75·77·103·104·117·122·128·129·142·152·153·156·163·167·173·188·206·224·226·231·236]⚖[5·10·12·14·21·22·32·47·55·89·92·106·107·109·115·125·127·130·138·139·180·184·186·202·204·211·220·233·238] ➔ >:-89 =:-100 <:-156) \n",
      "                    <:[9·19·28·30·47·54·57·62·63·66·70·72·77·79·80·81·82·88·89·99·109·112·114·120·122·125·128·139·148·156·160·170·175·178·179·187·189·193·194·204·206·214·223·233]⚖[8·12·16·18·21·27·37·38·49·52·56·58·60·64·84·98·104·110·115·119·127·135·141·144·145·146·147·152·162·164·168·174·180·183·190·202·216·224·228·231·232·237·239·240] ➔ >:-115 =:-131 <:-122)))) \n",
      "     <:[1·2·4·8·9·11·12·20·25·27·30·31·32·35·36·40·45·51·54·56·58·62·63·66·72·79·80·82·84·86·92·104·119·124·137·140·141·142·144·148·151·154·158·159·162·163·167·168·170·171·173·175·179·182·183·185·187·193·195·199·200·201·203·204·213·215·216·219·220·223·226·228·231·234·239·242]⚖[5·10·15·19·21·29·37·38·39·43·46·50·52·53·55·59·64·67·68·69·70·71·73·74·76·77·81·87·88·90·91·94·97·98·101·103·106·107·109·111·113·129·131·133·135·136·138·143·145·149·156·157·164·165·169·174·177·178·186·190·192·194·197·198·202·208·212·221·222·224·225·229·233·235·237·240] ➔ \n",
      "          >:[1·3·10·12·20·23·27·28·29·31·32·35·41·45·48·49·50·52·53·56·62·64·68·73·74·75·78·83·87·92·98·99·100·104·107·108·116·118·119·123·124·126·132·139·144·149·159·160·165·166·172·176·178·183·184·186·187·193·194·195·199·207·220·221·222·223·229·230·235·236·240]⚖[4·5·11·13·14·17·19·22·24·26·33·38·40·43·44·47·55·67·70·71·72·77·80·89·90·91·97·109·122·125·128·129·135·137·143·146·153·154·157·161·167·168·169·173·174·181·182·185·188·190·191·197·203·204·205·206·210·211·212·213·218·219·224·225·228·231·232·237·238·241·242] ➔ \n",
      "               >:[2·3·6·9·13·15·19·31·32·46·48·49·53·56·58·61·66·67·68·69·72·74·76·77·79·85·86·88·99·100·105·106·107·108·111·115·119·120·121·127·131·132·134·141·154·155·166·168·173·190·191·192·193·194·195·197·203·206·208·214·217·219·222·224·228·235·236]⚖[4·5·7·10·18·21·26·27·28·33·34·42·50·51·52·55·59·65·71·78·80·81·82·92·93·96·101·102·110·113·122·125·130·135·137·140·147·151·152·159·161·162·164·165·171·172·174·176·179·182·188·189·196·205·207·209·211·212·216·218·227·229·231·232·234·239·241] ➔ \n",
      "                    >:[71·81·129·131·173·185·201]⚖[51·55·76·82·109·204·206] ➔ >:-55 =:-5 <:-71) \n",
      "                    =:[5·20·22·27·43·49·50·66·68·69·72·74·80·82·89·95·100·116·133·136·139·160·163·176·188·191·196·210·211·218·226·234·236]⚖[2·17·38·39·57·59·60·61·83·106·112·114·129·135·143·148·152·156·162·166·173·175·206·209·213·214·216·217·222·223·224·225·232] ➔ >:-38 =:-70 <:-43) \n",
      "                    <:[3·12·22·28·32·44·70·77·83·122·145·162·182·198·200·205·206]⚖[4·45·51·67·68·72·75·86·181·190·197·202·214·216·230·238·242] ➔ >:-67 =:-19 <:-77)) \n",
      "               =:[3·5·6·19·21·26·33·34·35·39·47·48·52·57·59·71·100·104·107·118·120·122·123·128·129·141·150·162·164·166·170·177·188·194·195·197·201·202·211·214·219·220·223·224·228·230·231·233·237·240·241]⚖[2·7·10·22·23·24·25·27·37·42·51·65·70·72·76·80·81·86·91·96·98·99·105·110·112·117·124·131·136·139·140·143·146·151·153·158·159·160·167·179·180·181·187·190·192·205·207·208·216·226·238] ➔ \n",
      "                    >:[6·10·26·30·32·37·39·47·60·66·75·94·97·119·137·153·196·197·232]⚖[3·4·7·15·27·42·54·64·81·92·102·116·143·162·163·175·182·186·209] ➔ >:-81 =:-76 <:-37) \n",
      "                    =:[2·21·31·35·54·55·69·96·101·155·158·160·166·183·186·201·215·222·223·240]⚖[8·15·16·25·30·51·53·57·80·97·107·114·148·165·173·180·194·200·206·212] ➔ >:-15 =:-46 <:-69) \n",
      "                    <:[6·13·14·40·44·51·52·59·98·100·111·113·120·127·143·148·159·161·164·166·171·177·181·207·226]⚖[28·32·39·48·55·67·71·76·90·91·95·124·133·146·152·155·158·168·190·196·197·222·223·240·241] ➔ >:-39 =:-21 <:-59)) \n",
      "               <:[18·19·25·34·35·36·40·43·48·50·52·54·56·58·73·77·85·92·94·118·119·125·146·148·153·162·164·166·167·168·172·177·180·181·182·191·192·201·205·206·209·215·216·219·220·226·227·230·238·242]⚖[1·6·20·22·28·29·30·41·49·51·53·63·72·74·78·87·89·96·98·101·102·103·106·107·111·114·116·124·133·135·136·137·141·149·161·169·173·174·176·178·186·193·194·195·203·210·224·228·231·241] ➔ \n",
      "                    >:[1·2·18·21·22·32·36·44·46·48·51·57·59·60·61·67·74·77·80·82·83·95·98·99·101·107·110·114·116·120·128·138·141·145·154·169·192·194·195·196·209·219·231]⚖[8·9·20·27·29·30·38·40·54·63·66·69·81·84·90·92·93·96·113·115·117·121·126·131·136·160·167·176·190·197·207·210·211·212·214·216·218·226·229·235·239·241·242] ➔ >:-29 =:-53 <:-74) \n",
      "                    =:[3·21·26·36·39·43·68·70·74·77·80·85·87·97·101·108·115·121·122·131·142·153·157·160·165·167·170·171·178·181·197·201·204·229·232]⚖[4·11·19·29·30·37·45·46·50·53·59·63·64·65·69·96·98·100·102·103·104·133·135·144·150·174·195·207·208·216·221·223·228·238·239] ➔ >:-64 =:-10 <:-68) \n",
      "                    <:[5·31·52·62·75·84·117·137·140·141·156·161·169·170·172·174·179·192·206·212·214·215·218·224·234]⚖[10·15·28·34·41·43·45·56·57·67·68·70·73·77·85·111·125·148·151·165·171·187·188·209·231] ➔ >:-73 =:-50 <:-52))) \n",
      "          =:[3·7·8·9·14·16·26·36·44·49·52·59·61·62·65·66·72·76·77·80·81·83·84·85·87·89·95·96·99·102·106·109·111·112·114·115·119·123·124·126·129·133·137·140·141·142·143·144·149·152·155·157·158·161·165·170·182·184·187·192·199·202·204·208·209·210·213·216·217·220·222·223·224·225·226·227·228·233·239]⚖[2·4·5·6·11·13·15·17·21·22·23·27·31·33·34·35·45·48·51·56·63·64·67·68·69·70·78·79·82·86·91·92·94·97·98·100·108·113·120·121·125·128·131·134·139·147·154·156·159·160·163·167·168·169·172·174·176·181·183·185·194·195·196·203·205·211·215·218·219·221·230·231·232·234·235·236·240·241·242] ➔ \n",
      "               >:[12·21·28·29·30·33·34·39·42·47·51·53·72·76·77·78·80·83·92·97·102·109·128·144·146·155·159·160·167·172·181·187·188·190·197·213·217·219·221·228·234·242]⚖[8·16·17·20·22·26·32·37·48·50·55·57·63·66·67·68·71·74·94·99·110·113·117·118·121·130·134·136·137·139·154·171·176·182·184·185·196·203·205·206·224·241] ➔ \n",
      "                    >:[6·17·20·23·36·45·51·54·58·77·89·90·101·110·112·117·126·129·131·133·173·178·183·187·205·218·222·224·233]⚖[1·11·13·18·22·30·32·38·43·44·78·79·80·94·96·111·122·125·128·150·156·158·160·170·193·201·216·231·239] ➔ >:-22 =:-48 <:-17) \n",
      "                    =:[6·9·21·50·61·63·76·77·78·108·155·164·211]⚖[23·42·56·70·81·84·100·132·137·141·217·218·224] ➔ >:-23 =:-13 <:-6) \n",
      "                    <:[13·20·26·27·28·34·36·37·49·54·59·60·67·68·71·72·75·91·100·119·126·137·141·142·149·164·165·170·191·205·214·215·221·223·227·239]⚖[14·33·46·55·57·65·69·73·79·81·82·86·89·90·94·104·113·123·124·131·139·161·179·192·208·216·222·224·225·226·229·230·231·233·236·240] ➔ >:-33 =:-78 <:-34)) \n",
      "               =:[1·9·11·13·16·17·19·21·26·30·31·33·34·38·41·49·50·60·63·64·69·75·80·84·85·104·105·106·107·113·117·119·121·130·132·141·143·144·146·148·150·156·159·160·163·167·168·169·171·173·176·179·188·189·192·195·196·200·201·204·206·207·218·222·226·227·232·234·242]⚖[3·4·12·14·18·22·25·28·29·35·37·43·45·53·55·57·59·61·68·72·73·74·76·78·79·86·88·90·91·92·93·95·96·97·98·99·100·101·109·115·120·123·124·125·126·127·128·129·140·145·151·158·162·164·170·172·183·184·185·193·194·199·213·214·215·221·225·228·231] ➔ \n",
      "                    >:[3·5·25·41·44·46·50·51·56·57·62·68·69·75·76·77·79·84·86·95·98·99·102·105·106·109·110·114·123·136·145·146·152·155·158·161·162·167·169·170·171·177·182·193·194·198·200·201·203·212·216·221·223·225·226·233·234·240·242]⚖[14·16·17·21·23·28·29·32·43·45·48·49·55·58·64·72·87·89·90·91·94·97·101·103·104·108·112·113·115·117·118·120·127·131·143·148·150·154·156·179·181·183·187·188·191·192·195·199·202·204·207·210·211·214·217·222·229·237·239] ➔ >:-28 =:-18 <:-57) \n",
      "                    =:[1·6·36·37·42·43·46·59·73·80·88·96·125·131·143·144·158·160·165·171·201·217·220·233·236·239·240]⚖[13·14·15·19·22·25·30·41·47·51·67·70·81·87·93·109·110·117·118·121·127·163·166·195·205·212·215] ➔ >:-47 =:-24 <:-42) \n",
      "                    <:[17·19·26·37·41·49·52·63·70·90·98·109·113·117·128·130·131·136·137·140·152·156·164·166·174·184·189·190·199·200·207·212·222·225·233·239·240·241]⚖[6·8·11·24·28·31·32·42·46·56·60·61·66·73·79·80·82·86·97·99·114·149·150·153·154·162·165·180·192·194·197·214·221·227·229·231·234·242] ➔ >:-60 =:-75 <:-41)) \n",
      "               <:[1·8·9·16·18·26·29·33·38·42·53·54·55·56·62·64·65·68·78·85·87·89·93·94·95·102·105·110·120·124·128·140·149·151·153·154·157·166·175·183·187·188·189·190·193·196·197·198·199·203·213·220·221·223·234·238·242]⚖[6·7·10·12·15·17·21·22·24·30·32·34·37·44·51·61·70·73·74·76·77·81·82·99·100·103·104·106·111·114·121·122·131·136·138·139·144·161·171·174·177·180·181·185·186·192·195·204·207·219·222·224·226·232·237·240·241] ➔ \n",
      "                    >:[9·11·15·24·27·28·33·35·37·40·44·50·55·56·60·62·77·82·92·96·99·101·106·116·129·150·152·155·157·160·162·167·177·181·183·185·190·195·203·208·217·223·226·235·237]⚖[1·2·3·7·14·22·26·30·47·59·67·69·71·73·74·80·83·97·100·105·113·117·119·123·127·128·130·131·143·144·165·171·175·178·189·205·206·218·222·224·225·233·238·239·241] ➔ >:-7 =:-61 <:-44) \n",
      "                    =:[43·49·79·124·128·136·141·148·149·162·201·206·239]⚖[14·18·19·28·34·54·119·120·160·170·171·194·203] ➔ >:-14 =:-3 <:-49) \n",
      "                    <:[11·18·21·26·61·75·82·84·98·120·132·157·181·205·213·217·221·222·233]⚖[14·16·69·71·93·100·125·141·143·150·154·158·176·186·191·208·210·212·229] ➔ >:-16 =:-65 <:-26))) \n",
      "          <:[1·2·3·15·16·18·19·25·26·30·31·32·33·34·40·41·42·43·45·48·54·60·74·75·77·88·89·96·97·98·101·105·107·114·115·116·120·123·125·126·128·134·139·147·160·171·174·175·177·180·182·185·187·189·190·192·197·199·200·201·203·209·218·221·224·228·229·232·233·240]⚖[4·11·13·20·21·24·28·36·37·39·49·51·56·57·61·62·65·68·70·78·79·80·82·85·91·93·95·102·110·112·118·119·122·124·129·136·137·145·148·150·154·159·164·166·167·168·170·172·179·181·183·184·188·191·194·196·204·207·208·211·212·213·215·220·223·226·234·237·241·242] ➔ \n",
      "               >:[4·5·7·10·17·18·21·34·40·44·45·46·48·57·60·68·70·74·79·80·81·98·99·106·118·130·131·132·139·140·143·159·162·166·168·187·192·193·198·202·208·209·212·213·219·220·221·225·229·237·240]⚖[1·9·11·12·22·24·28·30·37·39·51·55·56·64·73·75·77·83·84·85·86·91·95·101·111·114·116·122·123·126·127·128·133·136·141·142·148·149·153·154·155·184·195·205·207·214·223·226·228·230·235] ➔ \n",
      "                    >:[26·40·46·51·83·84·85·87·127·136·139·163·180·199·202·221·227·234·242]⚖[11·27·28·43·44·49·72·75·111·117·123·143·144·155·189·190·208·209·210] ➔ >:-11 =:-56 <:-51) \n",
      "                    =:[5·8·25·35·37·45·51·56·57·62·71·73·75·87·90·104·119·148·156·187·192·194·197·209·226·228]⚖[4·6·16·17·20·29·46·65·67·70·84·88·93·97·98·123·137·142·153·174·183·201·219·220·225·238] ➔ >:-20 =:-36 <:-62) \n",
      "                    <:[2·10·23·34·36·38·41·44·46·50·53·63·76·78·80·85·91·95·101·106·107·113·118·133·134·136·137·140·147·155·159·165·188·192·199·200·202·204·205·224·232]⚖[8·12·13·15·20·25·35·39·40·56·57·62·65·74·79·83·84·92·98·109·111·121·123·125·128·138·142·143·146·167·172·185·194·196·211·216·218·219·229·231·237] ➔ >:-79 =:-4 <:-80)) \n",
      "               =:[6·9·12·14·16·18·19·23·25·30·31·32·34·37·48·49·52·53·58·64·65·67·69·70·73·78·82·83·85·86·87·89·90·91·96·97·103·105·107·110·116·117·118·124·132·133·137·143·144·147·148·151·159·160·161·164·165·167·169·171·172·174·177·184·185·193·194·197·200·205·208·209·215·220·225·226·232·233·236·238·239]⚖[2·3·5·8·11·13·15·22·24·26·29·36·38·39·40·41·50·51·57·59·61·63·72·76·77·79·81·92·95·98·99·101·104·106·111·119·120·122·123·126·130·131·134·139·140·141·142·145·149·150·153·154·155·157·162·163·166·173·176·178·181·189·190·196·198·204·206·211·212·213·217·218·221·222·223·224·227·229·231·234·237] ➔ \n",
      "                    >:[8·47·54·79·105·141·150·172·193·201]⚖[5·6·59·63·117·137·159·160·177·180] ➔ >:-63 =:-72 <:-8) \n",
      "                    =:[34·40·48·59·66·78·89·91·98·101·110·112·117·123·131·158·159·162·174·189·206·208·213·220·228·233·239·241]⚖[8·17·35·36·50·58·63·75·79·82·88·94·96·97·105·118·132·137·147·148·175·183·185·186·190·201·211·218] ➔ >:-35 =:-27 <:-66) \n",
      "                    <:[1·7·12·32·34·41·44·75·95·96·99·120·132·139·144·149·189·196·204·225]⚖[23·58·71·84·90·106·118·124·126·143·155·156·166·177·178·195·207·213·229·234] ➔ >:-58 =:-9 <:-12)) \n",
      "               <:[12·16·21·23·25·30·32·36·38·41·44·46·57·60·61·63·65·69·71·72·82·88·90·93·95·99·105·106·127·136·144·146·148·151·157·172·175·176·177·191·193·199·200·201·202·204·206·211·216·217·218·221·234·236]⚖[3·5·8·18·22·24·27·34·40·45·47·54·68·79·81·84·86·87·92·97·101·102·111·114·116·117·124·125·134·137·139·142·143·145·150·152·153·154·155·156·161·162·169·174·179·180·183·189·192·195·205·213·230·235] ➔ \n",
      "                    >:[36·41·54·64·67·125·148·179·185·231·235·239]⚖[14·19·22·40·98·116·127·161·164·177·193·203] ➔ >:-40 =:-45 <:-54) \n",
      "                    =:[1·13·16·17·24·25·27·41·42·46·49·51·55·59·68·72·81·83·85·86·87·89·96·99·101·105·107·123·127·132·136·140·142·143·144·149·151·162·164·165·166·171·174·183·184·185·199·200·208·218·225·234·236·237]⚖[5·9·12·21·23·26·28·30·31·32·35·36·38·53·54·56·58·60·62·65·69·70·71·79·95·100·104·108·109·110·115·116·119·122·131·152·153·168·169·170·179·180·186·187·190·192·202·207·210·212·213·227·228·239] ➔ >:-31 =:-2 <:-1) \n",
      "                    <:[25·54·57·74·82·102·104·110·131·132·161·193·202·207·210·212·224·241]⚖[1·3·5·19·29·32·60·72·76·103·116·123·126·155·169·200·209·216] ➔ >:-32 =:-30 <:-25)))))\n"
     ]
    }
   ],
   "source": [
    "do(Puzzle(242, 5, {-1, 0}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What's Next?\n",
    "\n",
    "- What other puzzles can you solve?\n",
    "- Can you make a table of solved and unsolved puzzles? \n",
    "- Can you prove the unsolved puzzles are unsolvable? \n",
    "- Can you prove that it is never necessary to put more than 1/3 the number of balls (rounded up) on either side?\n",
    "- What happens when it is a possibility that *two or more* balls are odd?\n",
    "- What about puzzles where your task is to identify *which* ball is odd, but not *how* it is odd. That is, if you get the possibilities down to `{-3, +3}` then you're done; you know ball 3 is the odd one.\n",
    "- Can you modify the `good_partitions` function to be exhaustive (but not redundant, and still efficient)?\n",
    "- Can you find trees that minimize the *mean* number of weighings, rather than minimizing the *maximum* number of weighings?\n",
    "- What else can you discover?\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
